It won't be a problem as long as you have a guarantor, landlord references and savings in case you have to pay in advance. They'll rent to anyone as long as they pass the referencing part of the process, which is not done by estate agents, but by a completely separate agency. If for any reason you cannot pass the referencing, you'll have to pay 6 months up front, which is not always a bad thing if you have the money because that means you get a 6 month break clause in your lease, allowing you to move out and take your new landlord reference with you.
We were told by one estate agent that it didn't matter how much money we had in our bank account, it wouldn't matter for the referencing company because we could go out the next day and buy a boat with it and not pay our rent! Great help, they were (Marsh & Parsons of Clapham Old Town). We ended up going with a private landlord.
I would recommend that you call up three or four estate agents in the area you are looking and ask exactly what their process is for a candidate like yourself. And make sure you go to at least one massive one, like Foxtons, just to get a well rounded idea.
Oh, and I'd expect 1-2 weeks for getting internet set up. Almost definitely one week, at least.
