Remember ATT are GSM phones so you can buy a sim card for overseas, pop it in and away you go.
Verizon only has limited world phones as it is a CDMA network native to the US.
I could be off a bit, but even though I have Verizon, ATT would be the better option.