As I understand it, the 'requirement' that landlords check immigration status before leasing to you becomes effective in April, 2016.
We had quite a bit of trouble finding a place to live from the States, but some of the difficulty was due to having a dog. The 'leasing company wouldn't allow me to sign as I wasn't yet legally in the UK, and my wife couldn't lease on her own because she was not yet employed. Even tried to give them a letter stating I was supporting her, but to no avail.
We eventually had to settle for a fairly expensive short-term rental in one of the suburban areas.
If you can find an individual who is leasing their property, it's a lot easier. Check gumtree.com for these, but be a bit wary of scammers (scamming is much worse on craigslist).