You guys talk much sense. Stick it on fuel and the amount you pay is directly proportional to the efficiency of your vehicle and your mileage. No mess, no fuss, no dodging, and the Govt will save a fortune as the mechanismn is already in place to collect it, they can save money by binning the unwieldy DVLA collection system, and they'll claw money back from folk who can no longer dodge it.
Set the tariff to start with so the average car covering the average mileage is cash-neutral when switching to the new scheme, and market forces can do the rest.
This alone would probably be a huge vote winner for whichever party want to grow some stones.