I heard a proposal to tax tires instead, which I suppose would let EVs and hybrids pay their fair share (although it would probably cause more cheapskates to drive around on bald tires)
Don't we levy road taxes on tires already? (albeit at very low rates)
Or just get new tires in a neighboring state.
There's a Federal-level excise tax on gasoline, so you could take that approach with tires. I don't think it's a great idea, though... too many people already drive on shitty tires years past their prime.