Any Android will work internationally. Sounds like you need to familiarize yourself with how GSM works overseas: roaming locked, unlocked with local SIM, data roaming, etc. If you travel with a locked phone you will have to "roam" for service and this can get somewhat, though not prohibitively expensive -- but ridiculously expensive if you don't shut down data-roaming. If your phone is unlocked, you can use a local SIM which is very cost effective if you are doing a lot of local calling. My G1 is unlocked but I have never felt the need to use a local SIM. When we're in Europe my son's at&t iPhone picks up the same cell companies I do with my TMo G1.
As far as "access to the various cell sites, the US, Asia, or Europe" goes, both at&t and TMo SIMs will "access" overseas carriers if you have them put an international plan in place (TMo it's free, not sure about at&t). Asia can be tricky. Your 3G will usually work, but you need to check country-by-country. It can get expensive.
The biggest issue is shutting down data roaming on Android phones as they have a history of being "forced" to look for data by certain apps. APNdroid (a market app) is what I use and it kills data. When in Europe or the Middle East I roam on GSM which allows voice and text (99% of what I need) and then I use wifi at my hotel if I need to check email etc. because it's free. I never turn data on. Whatever phone you buy, be sure it's a quad-band GSM (All Android phones are, I believe).