It took me one year to get a CC from bloody Lloyds. The same problem as a foreigner, I had no credit history in the UK and unbelievable but true, though we're allegedly all "united" in the European Union, banks don't interact with their foreign counterparts (and hence, my credit rating from Germany didn't count). You should try to bank with a bank that also is established in the US, like f.i. Citibank. One should think they have the resources to check your US history.
You could try getting a card with a low limit and pay off the balance every month. I did that and within a year they increased that limit 10 times! But you're right, each CC disapproval adds a record to your credit history. Therefore, try to get one from your bank first before applying anywhere else.