I'm looking for data plans I can use while touring different countries within a region without having to worry about being eaten by roaming fees. If such plans exist at all, I suppose mostly big telecommunication providers like Vodafone or T-Mobile will offer them.
My personal experience has been that it's best to get a SIM card for each country I travel in. Local providers almost always have the best deals, and buying SIM cards is relatively inexpensive.
Especially in Asian countries (where I have more travel experience) you can easily pick up SIM cards at shopping kiosks almost anywhere, and the rates are really very cheap compared to where I live (New Zealand).
Data roaming from international providers is also very expensive; as an example with my New Zealand cellphone provider in China I would pay $US25+ a megabyte, whereas buying a local SIM card it cost me $US8 for 250 megabytes.
It depends on what countries you are travelling to. If the country uses GSM, in most cases the best plan is to make sure you have an unlocked GSM phone, and purchase a pay-as-you-go SIM card in the country you are going to.
If you Google for "International SIM" you will see that there are tons of websites selling pay-as-you-go SIMs, and in many countries, they are easy to purchase on arrival at the airport if you know exactly what you're looking for.
A possible option is a global sim card, like those from GoSim. They work in nearly every country.
Another sneakier method, depending on what you need the data for and how fast it needs to be, is a 3G Kindle. It has free data to download books on Amazon's Whispernet in almost every country in the world, and has a basic experimental web browser on it. With a bit of effort, I've managed to get GMail, Google Maps, GTalk and more running on it - Facebook and Twitter even mostly work.
I guess you might be in the UK based on the networks you listed?
For within Europe, Vodafone are currently pretty good. Vodafone Passport means it's a single charge to answer/make a call, the rest is at the UK rate. If you're on a £40+/month plan, they'll give you 25mb/day/country of data for free, and 10 free texts a day
When I go outside of Europe, I just pick up a PAYG sim card, sling it in a spare phone and use that. Generally works out much much cheaper, and gives you a local number so people can call you easily from the country you're in.
My own best way to avoid data roaming fees when travelling is simply NOT to bring a cell phone abroad.
Making a phone call is easy from anywhere without a cell phone and internet connections are provided in many places in cybercafés.
Moreover, this is one object that you won't get stolen if it stays at home.
Best rates are generally had if you buy a local SIM. Alternatively talk to your friends via a Skype account over the internet. If you just want to make calls then there are a number of voice over IP providers besides Skype. If you want to receive calls buying a SIM locally is cheapest.
It's not an all-countries-proof method but if you're from the UK you could get a Three sim card, they have a Feel At Home system that allows you to use your plan in other countries*.
* At the time of writing (updated on April 2017): Australia, Austria, Belgium, Bulgaria, Channel Islands, Croatia, Cyprus, Czech Republic, Denmark, Estonia, Finland, France, Germany, Gibraltar, Greece, Hong Kong, Hungary, Iceland, Indonesia, Isle of Man, Israel, Italy, Latvia, Liechtenstein, Lithuania, Luxembourg, Macau, Malta, Netherlands, New Zealand, Norway, Poland, Portugal, Republic of Ireland, Romania, Slovakia, Slovenia, Spain, Sri Lanka, Sweden, Switzerland, United States.
There are quite a few pocket hotspots which have global or multi country data plans at much lower price points than roaming. I have a Glocalme U2, I have heard good things about the Pokefi which seems to be cheaper but covers a lot fewer countries. Also, the Glocalme U2 allows for -- but does not require -- a local SIM. Similar devices include the Skyroam and the Keepgo but I know nothing of those but seem to be much more expensive than either the Glocalme U2 or the Pokefi.
These are data only solutions but the question was about data in the first place, second VoIP is your friend if you need to make phone calls.