AT at MR has a pointed post on the "illogic" of a mileage tax, comparing it to a tax on breathing to punish smoking.
I agree that if your target is the reduction of environmental externalities (pollution and congestion), the fuel tax is sensible and the mileage tax is generally not. However, the history of the fuel tax (Hoover, Revenue Act of 1932; see this rather bizarre report from the US DOT) was a means of raising revenue to finance the expansion of public infrastructure.
To this day, it is a common example in public finance as a program that imperfectly follows the benefit principle of taxation. Those who drove on highways also tended to use gasoline, and hence those who benefited from the infrastructure were the ones financing it. The externality argument, as far as I can tell, came long after the 1932 act establishing the gas tax.
Conditional on the government both producing infrastructure and raising taxes to finance it, shouldn't the preference be for benefit principle taxation? So my basic suggestion is that, on the margin, libertarian outrage is better directed at other subjects, or at least at different angles of the mileage tax (privacy concerns, e.g.).