Fuel taxes by country:
Alternative Fuels Data Center: Maps and Data - Fuel Taxes by Country
Australia is actually quite low compared to a lot of (predominantly European) countries.
However other countries (like USA and Canada) are much lower than us. Canada has a similar economy to Australia - large country / low population - so a fuel excise (or road user charge) isn't the only way to fund roads.
We don't have a "user pays" system for many other services and infrastructure that is provided to the community by public funds - we don't pay to take the kids to the park, for example. Public education and public health are provided from consolidated revenue. Yes, those without kids are subsidising those with kids - so what? Likewise, roads do not have to be "user pays" - even if it means those without cars are subsidising those with cars. Their food and supplies are still being delivered by road.
We could just continue with the status quo - which is that fossil fuels attract an excise, and road use by BEV's does not. Call it an incentive based system to encourage adoption of BEV's. The current Federal Government is probably quite happy to do that, because unlike the previous Government, they are actually in favour of a transition to BEV's.
All they have to do politically is just quietly stop referring to the fuel excise as "contributing to the funding of roads". It never did, directly, anyway. Just let the excise gradually morph into a "fossil fuel tax". Just don't make the mistake of calling it a "carbon tax" because that phrase doesn't wash politically in Australia.
Once it becomes a noticeable hole in the budget (it wouldn't be yet), that hole just needs to be gradually filled with an alternative source of revenue (or, God forbid, maybe reduce spending).
Just need to make sure that whatever contribution the Feds used to make to the States to fund their roads continues, and the States actually have nothing to complain about - as far as the States are concerned, there isn't a problem. Funding any deepening hole in the fuel excise revenue remains purely a Federal concern.