Good cities for gluten-free vegans?
I don't know how other cities are, but Madrid has stores called "herbolarios" in nearly every neighborhood that sell gluten-free products (and spices, grains, beans, etc.), so as long as you like to cook, you can eat very well. You can also get gluten-free products at supermarkets like Mercadona. Spain has great dried, jarred and canned beans--not to mention veggies and fruit. But in regular restaurants all bean dishes have at least a little meat or egg (my son is allergic to egg and it is hidden in a lot of places that you might not expect). There are a few restaurants that have strictly vegan food... and a growing number of good chinese places with lots of vegetarian options (one of our favorites--Buenaventura in Plaza de la Luna--has a lot of dishes that should be vegan).
It will probably be tough but it's doable. I have a Spanish ex-sister-in-law who's a vegetarian and always had problems eating at "normal" restaurants and seemed to rely on Asian restaurants. She especially liked an "asian tapas" place called Mosquito in El Born. If you find yourself at a regular restaurant you'll have to make special requests and you might be bored but you won't starve- it will help if you can understand and speak a little spanish (or catalan).
Damm brewery, of Estrella Damm fame, makes a gluten free beer that is pretty widely available.
There are plenty of artichokes, padron peppers and roasted vegetables around (escalivada is a common Catalan dish of roasted eggplant and peppers, just make sure they don't throw any anchovies in or on top)
It's not true that all beans have meat in them. Most beans dishes do but it's very common for places to have plain beans that are cooked without meat, they're just usually accompanied by sausage. I'm sure restaurants would be willing to leave the sausage off (you'll still want to make sure there's no meat involved). You can buy pre-cooked beans in every market if you're cooking for yourself.
Since I don't follow the same diet I can't offer much more besides that and the big generalization that there are lots of young "lefty"/anarchist/straight-edge types in Barcelona and I'm sure many of them follow a similar diet, there might be online sources from those communities that can help too (sorry for the stereotyping, no offence intended)
Check out www.happycow.net for vegetarian options throughout the world.
I know you didn't ask about Portugal, but if you should go to Lisbon you should not mix Restaurante Oriente Chiado, a terrific upscale vegan buffet-style restaurant, and the owner/chef is charming and friendly, too.
Sorry, I don't mean to sound negative...but are you sure you want to visit Spain...the land of the hanging jamon? Honestly, It is incredibly hard to find vegetarian food...gluten-free as well-i wouldn't know where to begin. Prepare yourself for a big challenge. Gazpacho even has bread in it! And the olives here are often stuffed with anchovies. Your best bet, if traveling in Spain, is to stay in a place where you can prepare your own food and shop the markets...which do stock beautiful fresh fruits & veg.
One of my friend's girlfriends is vegetarian - not vegan - and when she comes to visit him in Spain, she mostly gets by eating in ethnic restaurants - Indian, Chinese, or Italian. Spanish restaurants, for the most part, still haven't grasped vegetarian cooking. Once she ordered what was listed on the menu as a "vegetarian" bocadillo which came out with lettuce, tomato, & TUNA. She had to send it back 4 times, before they understood that vegetarian means NO tuna. Another time/another place she ordered gazpacho which was served with bits of fried pork rind as garnish. Unbelievable.
By the way, we are in Valencia...I'd like to think things are a little better in Barcelona or Madrid. My Time Out Guide to Barcelona lists 3 "vegetarian" restaurants in Barcelona...Juicy Jones, Organic, & Sesamo. Hopefully someone else out there has better insight. Good luck!
Even in 2008 there were much, much more than 3 vegetarian restaurants in Valencia.
Here's an old thread - do make sure you call ahead to ascertain whether the places are still in business
The region with the traditional food that best accommodates your dietary requirements is, in my opinion, Murcia. Most of my favourite meatless recipes come from this region. Here is a selection of some well loved examples that are also gluten free
http://www.regmurcia.com/servlet/s.Sl... - this usually has salted cod, I've substituted this with a couple of spoons of Marmite which does the job beautifully
Murcian style gazpacho has no bread (which means there is debate about this actually being gazpacho
http://www.regmurcia.com/servlet/s.Sl... I personally like olla gitana with pear
As has been suggested, you'll get to enjoy the food and have a greater chance of eating traditional food if you can find accommodation which will allow you to prepare it yourself. A great deal of the foods from the East coast are actually ideal as rice is the main grain and meat was expensive for most of the population. The pork bones or slices of sausage that fill out so many of the traditional dishes and stews can easily be substituted (try heating olive oil in a separate pan and adding chopped garlic until just about to brown then adding paprika for a couple of seconds; pour this hot flavoured oil onto your nearly completed guiso and you'll hardly notice the lack of cooking chorizo.
Barcelona should be very good for people with such special diets. I recently helped a celiac friend plan her trip to Barcelona. Here's a link to a pdf file from Celiacs Catalunya.org. You can also get a paper copy of this guide at the office of tourism under Placa Catalunya. The guide contains pictures of restaurants, what gluten free items they serve and a map to show where they are in the city.
Sincarne is a good resource for vegetarians too.
For shopping, El Corte Ingles at Placa Catalunya is the biggest department store and they stock gluten-free food. Daura is a gluten-free beer made by Estrella.
I haven't tried any of these places myself since I go to Spain for the jamon too. :-)
Instead of coming all the way to Spain and being forced to choose only a handful cities because of your extremely restrictive dietary habits, why not go anywhere you want but rent an apartment with kitchen and have control of all your meals?
Many of us choose specific dishes depending on which city we visit.
Doing the opposite, being forced to choose a destination based on such severe constraint is just too tragic for a country like Spain with its extraordinary richness.