I like the appoach of paying for the road use as a variable component of the normal license-renewal fee (here in Oregon, the once-every-couple-years purchase of new plate tags). Owners of ICE vehicles in metropolitan areas are already required (although maybe cars less than X years old get a pass; I forget..) to obtain a "meets pollution standards" certification as part of the renewal process, which involves visiting a station where a connection is made to the car's network and having the state's equipment ask, "have you been a good little car?". The infrastructure for doing this (here anyway), is already in place, and I understand the cabled interface is standardized, so probably the EVs meet it already. It should be easily possible for the EV manufacturers to implement separate "miles driven within jurisdiction during XYZ time period" odometers that could be queried & reset at these stations in the same way as the "did your pollution controls work?" queries are done now, and for the answer, in miles, to be multiplied by some reasonable per-mile road use fee, which would be added to the tab renewal fee just like the current "clean air inspection" fees are. Heck, the fee could even be easily adjusted according to the weight of the vehicle.
Best of all, this system of road-use fees would be applicable to ICE cars too, as long as they had an integrated GPS, anyway. And I think it avoids privacy-invasion issues pretty well; drivers wouldn't be disclosing their destinations, only the fact of having driven X miles *somewhere* within the taxing jurisdiction.