Thanks for bringing the topic of international travel, which is important for many Android owners. As for my recent experience, I just traveled for 3 weeks in China and only had my Verizon Droid Incredible (CDMA-only). Much to my surprise, Verizon actually offers CDMA service in China (1X only though). While doing some research before I left, I found out that Verizon actually offers an unlimited data plan to several countries (including China) for the VERY reasonable price of $65/month. This $65/month data package will replace your $30/month plan (it's not an additional fee) pro-rated for the time you want to be overseas. So for my 3 week trip, I only ended up spending ~$26 in addition to my normal phone plan and had unlimited data usage. This does not save you on your minutes, though (still $2/min). And make sure to use the generic WiFi Skype app rather than the Verizon-specific 'Skype Mobile' which will still count against your minutes even though it is only data.
Verizon doesn't really promote this data plan very well, and it is hard to get information about it outside of the Customer Service reps, and some web forums. It is called 'GlobalEmail', but I verified with at least a half-dozen customer reps that it also allowed for internet (non-email) data as well. It was amazing to have access to Google Maps the entire trip! Just don't try tethering your laptop to it (officially or unofficially) or you will risk data fees of $20.50/MB (That's right, it's $20,500/GB without this plan).Anyway, I hope this helps:
Link