Having a free society doesn't implicate on having no leaders or structured groups it just means that no leader shall be able to initiate force and any leadership should be forced on any individual that doesn't want their leadership
I agree that this is how it should be. But governments started out as leaders who got more and more followers and obtained more and more land. What will stop power-hungry people from forming another government?
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