What's interesting is that I signed us up for Tesco bank account but we were both rejected. Probably because we didn't have any history in UK yet but it still kind of sucked - now I am glad they rejected us. Ultimately the next day we went to red and blue US bank on the high street and got it all sorted within half an hour. We showed them contracts, documents and bills to our names (real estate agency through which we rent already sorted that out for us before we came) and we were done. Got our cards made at the spot as well.
So it was kind of the opposite for us. We could't get the bank account with Tesco because of their "security check" but could at the high street bank.
Some banks even allow opening the bank account over the internet if you are a EU resident.
(I know your pain though, opened a UK bank account a year ago, from the EU as well. The most difficult thing for me was actually the proof of address. Metro Bank required 2 plus 2 proofs of ID, a different bank was fine with just one proof of identity and even googled my post code when I forgot a letter :) )
You don't need to prove a UK address, just an address. Depending on the bank, you can open a UK bank account with an overseas address, and change it after you move.
If you haven't planned ahead, then anecdotally Barclays will open an account in branch with only a passport.
http://expatriates.stackexchange.com/questions/85/how-to-ope...
That's how I got my first UK account.
I told them to sod off and to look up the company in the company house.
Passport Accounts in the UK are pretty limited with what you can do with them, so I don't advise opening one up front if you planning to immigrate.
Just ask your employer for a cash advance and either use cash for the first 2-4 weeks or use your debit/credit card from your previous country of residence.
When I relocated initially I've arranged that the employer will cover the hotel upto 6 weeks, provide everything needed for a bank account, provide/cover the accountant needed to sort any tax liabilities when moving funds, cover the deposit for the first rental and the agent fees.
If you are hired by a large corp which does relocation all the time they'll have a standard and even a better package, if they company doesn't do relocation on a regular basis make sure all your sides are covered.
Otherwise you can land in a limbo state where you need a bank account to rent a flat, and you need an address (a hotel won't do) to open a bank account (they ask for a utility bill).
I've been working in a variety of EU countries, with no issues at all. In Denmark, I was even able to secure a mortgage within my second week in the country.
I always work for very reputable employers, with long-term contracts. And I have some savings. Well, here in the UK I have had enormous trouble to lease a £100 / month car after 2 years in the country because I did not reach 3 years of credit history.
Most of the heuristics they use are a joke. And illegal. If you have a chat with the Financial Ombudsman, he can probably sort you out.
I escalated this to the Ombudsman, just to piss them off for the poor treatment... magically they offered me a SIM and an (half-)apology.
The various id requirements and 3-year credit history expectation are basically workarounds for this.
I normally use the phrase 'High Street bank' to mean those that have a branch on most high streets and range from unhelpful to really unhelpful. That's useful to know that Metro bank are living up to a different reputation.
As far as I know, they're not related.
These are people who may have to pay rent more than once a month, have direct debits for bills and more likely than not not have an overdraft over 100£ if at all.
If your bills bounce you will end up with fines, and even a lower credit score than the one which prompted you to open an account with Tesco in the first place.