You need to phone BT they run all the phone exchanges. Get a phone line installed, then worry about a ISP
As for the speed you require, there are areas (quite a few) in the uk that cannot get xDSL at all (when copper got expencive in the 70s/80s BT messed with other methods of installing phone lines in to new homes)
Hope you can get it first before you worry about 4mb
ANYHOW
Check
http://www.adslguide.org.uk all the xDSL ISP are listed here, with speeds limits and costs. They even have some forums for every ISP so you can read what other users think about AOL/bulldog etc
Id advise going with
http://www.pipex.co.uk ive been with them since before the days of broadband and have had very few problems (and when i have they have been resolved quick)
God im board ;/