Capital One's Classic card is often recommended for people who have difficulty in getting a 'normal' credit card. It's got a really high interest rate but it's useful for people who, for example, want to buy goods over the internet but can still repay the full amount each month. It's also useful for helping people create, or re-establish, a good credit rating.
The application form does have a question asking how long you've been with your current bank or building society but the form permits you to enter '0' if you've got no bank account.
I'll repeat the warning about that really high interest rate but, depending upon your needs, it might be useful for you:
http://www.capitalone.co.uk/web/raid/templates /cardlist_temp_10_001.jsp?page_id=10200&contex t_id=2&pageId=10200
Chris