I have never been charged agency fees, in 18 years of living in rented accommodation in London! I was charge £60 for a reference check in my most recent property.
As for the deposit issue, if you have no credit history, or poor credit history, or have no guaranteed income (ie self employed) then you will usually be asked for a guarantor, who agrees to become liable for non-payment of rent in the event that you can't pay. So, when there is no guarantor and no credit history, as if often the case with new arrivals to the country, landlords have to ask for large deposits. You must make sure this is to be held in a deposit protection scheme.
Vicky