I have rented from a private Landlord in the past when I was freshly back in the country and didnt even have a UK bank account. It was a huge problem until I just offered to pay the entire 6 months in advance - at which point I had two Landlords practically fighting over me. I was in a lucky position of having the cash available, but 6 months rent at ?750 is ?4500 which might be possible with a couple of months hard saving, shoving it on a credit card, borrowing from a mate, looking down the back of the sofa or a combination of them all.
Throwing money at a situation doesnt fix every problem in the world but this is one which it most definitely does!
R xx