I realise the economic situation may be different than 8 years ago when I moved over (that said, that was just after the crash of Northern Rock and all those other crashes), but I too was on a work permit seeking a personal loan.
I first got a credit card (issued with the bank I had my current account with), with not a great interest rate, but worked. I built that up for a good 6 months and then went for a personal loan with the same bank as the current account/credit card to pay off US debt and avoid those exchange rate headaches. I was originally declined and I was gutted. But it turns out that my issue was that I was trying to get a loan for 5 years (out past the terms of my visa) for lower monthly payments. Once I set it to 3 years, well within the terms of my visa I was accepted. Made my monthly outgoings for the next 3 years quite painful with high payments, but I paid off all my US credit card debt (which was quite huge for many reasons, with crazy interests rates, so was definitely worth getting the loan for).
Anyways, really, my aim was to give you hope that it can be done, with some persistence and patience. Good luck!