X-Ray,
RBS obviously suck ass, cos (deep breath):
I've had an account with lloyds for 7 years, intermitently on the dole for some of that time, after a short peroid of JSplus last year I got a job, applied for a Credit Card from llyods, got turned down, then in 2 months (still with job- part time low wage)I opened a Internet Paypal thingy, went into the bank to sign up for internet banking, and to check the paypal intro payment thing, and they practically tried to shove a credit card down my throat! Which was nice.
So:
Be with a bank for a while
Express interest in Credit card
Have regular income for a while
and you're home free!
And once you have one Credit card with a good record (I tend to pay as I go, then I don't get carried away!)you can apply for a better one somewhere else.
