Without a credit record, AT&T will ask you for USD Protected content before giving you a mobile phone subscription. The other companies might not be easier to work with either.
If you already own a mobile device, avoid the hassle and go for a prepaid plan (no deposit, no silliness with drivers licenses SSNs and so on).
I never paid much attention to prepaid rates before, so I was surprised to discover that they can be cheaper than a regular subscription, sometimes even with features like free calls and SMS's to European landline numbers.
The only disadvantage to these models seems to be their ineligibility for international roaming, so you might want to get yourself a similar local SIM card to use during "home leave".