EggCard seems to market to people who have not-so-good credit ratings, so perhaps they'll be willing to issue cards to people with no credit history, as well? I applied for an EggCard in my husband's name, which they issued no problem, and I am an additional cardholder.
When I opened a current account at HSBC, they asked if I wanted a credit card (to which I happily responded "yes!"), and they issued me one without a problem. At first, it had only a £500 limit, but it was better than nothing.
I also have credit with Freeman's, which is a mail-order catalogue company. I'm sure that helps to build credit, as well.