Even Lloyds is hit and miss. A general strategy that seems to work is to gather as much documentation as you can (work contract, flat lease, any government paperwork, something that documents your address and status where you come from, anything with the address you live at, even if it doesn't have your name on it etc) and hit the main street banks from one end, eventually one will bite. Don't worry which one you get, you can easily change it later - all you need is for any bank to send you a statement.