Frank, definitely tougher to get things established when you can't be added to your S/O's council tax bill, etc. However, not impossible. Since you're tier 2, a letter from your employer may go a long way with the banks, saying you're an employee, on their payroll, etc.
Also, it may be easier to go the other way around, setting up a place to live first then getting a bank account. Many private landlords don't object to setting you up on the lease if you pay them 1 month rent in cash and the deposit in cash upfront. Then you can establish an address, get to the bank, and then you'll be able to direct debit-cheque-whatever with a landlord. Worth a thought anyways!
Good luck!