This is kinda devils-advocate-y, but it's worth remembering that if the world is a certain way, there's probably a reason for it. The fact that pretty much all of the livable land is either controlled by relatively powerful states, or occupied by tribal people with beliefs entirely incompatible with libertarianism, tells us something about how the world works.
If you want to form a country, or some entity with sovereignty over a decent-size plot of land, then you're going to need a military. That military will have to actually be loyal to the government/leadership and the population of that place. If you don't have that, then some other more established country will come take over, or at least have such strong influence that they are de facto in charge.
That's why I don't think pure libertarianism is tenable - if you don't have some sort of powerful state, then some other powerful state will come take over your society. There's still plenty of room for debate on exactly what the role of that state is, and how the leadership is chosen and laws are made, but I don't think you can ever get around that. It's kinda like claiming that total pacifism is the best philosophy, but it never had a chance because all of these other big meanies keep squashing it. Like it or not, those big meanies are part of the world too, and if your philosophy can't handle them, then it's no good.