Your main hurdle is a regulation called Know Your Customer, which requires banks to have some idea of the actual identity of folks who bank with them. However, banks have wide latitude in satisfying KYC. Some will accept a faxed passport/driver's license combo, for example, others can direct you to an affiliate in a foreign country. CitiBank, for example, will happily open an American CitiBank account for a Japanese citizen who walks into a Japanese CitiBank and asks for help with their international banking needs.
There are other ways. One which used to work but which I haven't tried recently is to open a brokerage account -- which have very lax verification requirements -- with ETrade or one of the other international low fee brokers. They're quite used to having folks abroad open accounts to invest in the US markets. After you have a brokerage account, ETrade knows you for the purpose of KYC, by reference to your "pre-existing business relationship". Then you call up ETrade and say "Hey, you're also a bank. I'd like a checking account tied to my brokerage account." Bam, done.
After you have one American bank account getting a second one is a cinch, incidentally. (cough ING Direct cough.)