I would carefully scrutinize the T&Cs for secured cards....look at their fee structure and also how often you can bump up your deposit to increase your CL.

Do a search in the CC forums on "secured" and you should be able to find some good information on secured card choices.     You might be able to get in with a store card as well, perhaps target or a GE card, although your CL might not be much to start with.

I wouldn't worry too much about the address right now ~ you can always deal with that later.    Once you have positive tradelines reporting, then your current address should be reported too.