Violence can be organized without being centralized; justice can be meted out in a manner that derives from human action without being a product of human design; law can be coercive without being a vehicle for subjugation of some group over another. That is in fact what societal norms, market law (Law Merchant, Law of the High Seas), and societal judgment systems like the Moot were for.
Consider how much of human behavior is pressured not to occur, not by statutes, but by basic shunning and tacit threats of violence (or what can be worse: ostracism) from peers, colleagues, friends, and family. Would is scarier and more life-uprooting, to serve 2 years in prison or to have everyone refuse to trade with you for 2 years? Most people would likely not survive the latter.
Now what is it that dis-enables such ostracism in modern life? Large populations and the ability to move. You don't need reputation to trade, because the state provides its own laws for bad actors. But these are exactly the areas Bitcoin addresses: with ubiquitous decentralized online money, we can have decentralized reputation systems. In the future it will likely get harder and harder to do much of anything without a good reputation in this decentralized system.
Tribes exceeding Dunbar's number (50-200 people) become less and less problematic when we can truly have systems that effect a Hayekian "extended order" to help regulate societal behavior en mass. It will probably feel somewhat oppressive even, though a far cry from state justice.
Keep in mind also that things like Bitcoin are simply state weakeners, not necessarily absolute destroyers. They might wither away all power structures larger than the government of a mid-sized city, but leave the rest intact.
In any case each step toward decentralization of money, reputation (legal action), trade, education, information sources, etc. - all the pillars of state power - will almost by definition weaken the fabric of governments. This is not even getting into Daniel Krawisz's point about Bitcoin's allure for government agents, which could really unweave the very yarn from which state power structures are woven.
For elaboration on what factors affect whether societies will end up centralized or decentralized, and why Bitcoin affects this so much, see the following posts and essays, as well as linked content therein:
https://archive.freecapitalists.org/forums/t/8889.aspx
https://bitcointalk.org/index.php?topic=230416.msg2450191#msg2450191
http://faculty.msb.edu/hasnasj/GTWebSite/AnarchyDraft.pdf
http://www7.tau.ac.il/ojs/index.php/til/article/download/694/653
[Edited to fix links]