No credit card required
Browse credit cards from a variety of issuers to see if there's a better card for you.
OP,
As it has been suggested, you need to check if you have an SSN or an ITIN – if you have the latter, I don't know if you can get a CC in the US.
If you do have an SSN, then applying for a (secured) CC at your local bank branch (and getting approved) is probably the best way to get your data sent to the CRAs.
It could be that doing the application face-to-face at your bank may help it bypass some preliminary checks – something which would not be possible with an online application. Once your card is approved, you will be able to start your credit history. Make sure to mention to your bank that this is your first-ever CC, because it may help them understand why they will not be able to pull your reports. You will probably have to bring your SS card and other supporting documentation for your application too.
This is to the best of my understanding. Anybody please chime in if I got something wrong.
The problem is not with the databases, but with SSN Randomization. Even before they go to the databases, they run a small program called SSN_validator, which checks that first three digits of your SSN are valid. In June 2011, Social Security changed the algorithm. For example, SSNs starting with 734 to 749 were invalid before June 2011, but are valid now. Unfortunately, nobody bothers to update the SSN_validator, because it only affects immigrants and 2-year old Americans. Be patient, wait a few years, eventually it will be fixed.