To achieve a free society/a stateless society the people living on it need to have done it themselves and have a libertarian mindset(the new libertarian manifesto talks about achieving anarchy with your actions), i believe that they would not let something like this happen again because they will remember the tiranny of the state and all the bad things that come with it, and remember, there can be multiple govermments, there will be people who will prefer to live on a govermment, and its fine as long as there is consetiment of all the people involved on it, you can't say for example that an unborn child of a citzen of your govermment is bound to this govermment because his parents signed a contract, because they dont "own" the child, it has self property like any other human being, what they own is the right do guard and take care of the child (Rothbard talks about it on Chapter 14 of ethics of liberty: http://goo.gl/BCKDTg ).
Govermments can exist, but not states, only with time the existing govermments will start to fail and people will abandon the idea, or not, because govermments in a free society arent mandatory, you can leave them (unless you signed a contract saying you wont) so they become like any other private business and compete against each other on a free market, if they do something against your natural rights or against the contract you can sue'em on a private court or stop participating on it, they dont really have any stimulus to be tiranic, because there will be non tiranic organizations competing with them