I'm going to assume that you're doing this with their knowledge and permission...

Do they have a relationship with a local bank? You can often get a low-limit credit card that way. Secured credit card is another option (you give the CC company cash up front and draw on that). credit restrictions are higher on rewards card/annual fee cards. Maybe try starting with a free, no frills, no/low rewards card. Citibank, Capital One are decent options for cards like that. Also, maybe instead of applying online call and speak with a representative. Explaining the situation over the phone to an actual person will probably help you get somewhere.

Also, they pay utility bills right? Some utility companies will report good history to the credit bureaus, but you often have to request it.