I had to get my US bank account to print my UK address on their statements and mail them to me - - - I used *that* as proof of residence in the UK since the utility bills etc were all under my husband's name. After I got an account (with HSBC) I had my US bank change my address BACK to the US. bit sneaky, but the lady at HSBC actually told me to do it!

So yeah, it took quite a while to get an account. HSBC ended up being fine with me though.
But each branch will be different. While there are general rules about what they are and aren't allowed to do, it seems like sometimes it just depends on the teller you get! So you'd go to a bank (maybe several) and ask them exactly what you need to bring in for an account, then work from there.
I had a HORRIBLE time with Abbey National. They wouldn't give me a current account (read basic checking account) becauase I hadn't lived in the UK for at least 3 years. THey Would Not go around this, even though I had a job and needed an account to deposit money into! They finally gave me a savings account, but it didn't work and my employer had to cut checks for me much to their annoyance.