You wouldn't replace it with anything. You'd need a cultural change where people recognized that stealing is always wrong, even if they call it taxes and declare it legal. Police and courts would be businesses like any other and not funded by force.

As for examples, America was founded in liberty. Unfortunately the nightmare scenario is playing out in real time as the US evolves from the tiny government of two centuries ago into the police state of tomorrow (today?). All libertarian societies I'm aware of eventually give way to the nightmare of the state. So, nope, I can't give you any examples of a libertarian society that lasted indefinitely. But brief liberty is better than none.

The only way I can see liberty playing out in a sustainable way is if the entire planet becomes libertarian so that there are no giant concentrations of force capable of taking it over and turning it back into a state. And I think this will eventually happen since it would continue the slow but steady moral advance of humanity.