The main roads (most A Roads, all HQDC's, Motorways) should either have segregated cycle facilities or a suitable alternative route (of no significant extra distance), as should some of the busier B roads.
Below that roads will either be lightly trafficked country lanes where, provided sight lines are good, there's no real need for segregation (at least for the time being), or destination streets where the only people on them should be cyclists or people arriving at / departing from there destination and should therefore be subject to a 30km/h / 20mph limit.
As for on street cycle paths - I have to agree with Stevie D - although I would narrow the "car" lanes and put a cycle track up one side of the street (with a kerb between it and the road) and start prioritising pedestrian and cycle access across junctions (especially entering and exiting side roads).
Most places where on road facilities have been provided there is the space to do this, with perhaps a marginal loss of footpath width (moving all the junk (lights, bins, trees) to be in a single line would be a useful start!
I want to know which idiot came up with the Castle Boulevard scheme - a lane which randomly disappears for part time parking bays, then reappears, the occasionally loops round the parking bays http://goo.gl/maps/Fe1G
and the vanishes for a junction. The better plan here would have been to put the parking bays on the northern side of the road between the trees, leaving the pavement the same width as it is around the trees - tidying up the south side pavement a tad, then building a two lane cycle lane with kerb separation from the road - leaving the cars in narrower lanes (to encourage a more appropriate speed for the road) and removing all the pedestrian refuges but replacing them with a couple of Zebra crossings. Down this stretch it's not as if there are any busy roads to the south - they are all car park accesses, primarly for small businesses, offices, and apartments. You could even provide a similar scheme down Lenton Boulevard using the existing off road cycle path at the eastern end, Alderney Road and Hungerton Street to provide a bypass of the roundabout and allow both cars and cyclists to have better sight lines when crossing at a light controlled junction. Something along the lines of http://goo.gl/maps/Mu9t
shouldn't effect the traffic too much, yet would provide massive improvements for cyclists.