Opening an account can be difficult in these circumstances. You usually need some proof of a UK address. Because of money laundering restrictions, this is harder now than it used to be. But there are still two ways you can go about it:
- Doing it yourself, and
- with assistance.
1. Doing it yourself
The banks differ in how much identification they require. I looked at a few for you. Some require you to apply in branch, e.g. Barclays. For the rest of this answer I've focused on HSBC, which lets you apply online and seems to make the process easiest for foreign nationals.
You will only be able to open a basic current account to begin with – i.e one with no credit (borrowing) facility. However these accounts usually have all the features you need such as debit card and online/mobile banking. This type of account is OK for sending and receiving electronic payments – so it will be enough to get you started with receiving your salary and setting up transactions such as your bill payments.
You mentioned you have your VISA and job contract. Along with your passport these fulfil the identity requirements.
It's important that your current address can be verified as well. Take a look at the specifically the section on address verification documents in the following:
http://www.hsbc.co.uk/1/PA_esf-ca-app-content/content/pws/content/personal/pdfs/basic-bank-account-identification.pdf
So a letter from your UK employer to your home address should fulfil this requirement.
2. With assistance
The website Work Gateways offers an assisted service for £35:
http://www.workgateways.com/moving-uk/uk-bank-accounts
Their "Kickstart" service includes setting up a bank account for you at Barclays, TSB or Lloyds. It is designed to take hassle out of the process for you, and offers additional help such as meeting in London, providing a UK SIM card and so on (details on the above link).
You do not need this service if you are willing to do the steps in (1) above; I just thought it might be helpful for you to consider it.