Radiators work independently of the way that the water in them is heated, so you shouldn't need to change them.
As with any work by tradesmen, I'd suggest getting an absolute minimum of three quotes. (Five would probably be better). This should include both large and small firms.
A good starting point, though, might be to find out how much it would cost to have a gas supply connected to your house. For this, you'll have no real choice other than to contact the local distribution company for your area. (You can't avoid using their services because they have to install the metering equipment). The majority of domestic connections, in mainland Great Britain, are provided by National Grid but there are four other regional companies. You can find out which company serves your area by consulting the map, here:
http://www.nationalgrid.com/uk/Gas/Connections /domestic/
Chris