To follow up, when I arrived here I needed a bank account for work to pay me, so I went with HSBC. They offered me a CC right off the bat.
I think it was so easy for me because I came over on a Tier 2 visa with a decent income coming in. From what I've seen here, everything seems to be harder on a spouse visa, though I'm not sure why.
Going forward I have my AMEX and HSBC cards, and I think that'll be enough for a while. The whole point for me is to build credit (and squirrel away money for a flat), so I'm not looking to get myself in debt to my eyeballs. Just enough that a bank will give me a mortgage

I might get try for a Tesco Clubcard CC just for the points and convenience.
I don't see myself going back to the States ever, but I'm going to keep my American CCs just so that if I ever do, I'll have credit there too. I'm going to use them to pay for apps on Google Play so they get used, but the charges are minimal.
Sent from my Nexus 5X using Tapatalk