From Bob
Instead of "how" to build a state in a non-state environment, an equally important, if not more so, question is "WHY" build a state in a non-state environment??
From The Curmudgeon
I have to keep telling myself that "how to build a state in a non-state environment" is the name of the thread but it seems that we (the successful states) are forcing the lessor developed territories into a mold that requires more than they can sustain. It is expensive to keep the huge bureaucracy associated with a state (particularly its external relationships and defenses). It requires the development of a cadre of experts and bureaucrats - years of training. It requires an education system to train those experts and bureaucrats. How do you do that when you have no economic base?
It seems to me that the first mission after establishing security is establishing a functioning economic system. The government could be a caretaker system at this point working "by, with, and through" the local leadership (most likely tribal leaders at this point). Once the economic system is in place (or concurrent with its establishment) you can start to build within the limits of the capabilities of that economic system. Don't try to build a Rolls Royce when all you can afford to maintain is a Hugo.
I tend to agree with both of you that the problematic of building a modern State in a non-state context is bound to the need of external powers to have an interlocutor. We are definitively in the dictate of the norm as defined by Foucault. A dictate for us rather than for them, by the way.

But never the less, governance does exist in non-state environment, therefore it should be possible to establish a form of government that is acceptable for the populace.
Also, as you pointed very well, the main problem to establish a state is in the need of tax collection by the state.
One of the reasons why there is so much resistance to the establishment of a state in Somalia is the question of taxes (among many others). But even Al Shabab do collect taxes. They collect them through religious taxes or other protection revenues but they do collect taxes.
What they sell is not security or protection; it’s a simple form a basic racket: if you do not pay, then I will harm you.
Do not forget that in a non-state environment; almost 90% of the population is economically not in capacity to pay any taxes. Therefore, the one who will pay taxes are the one who do already control the economy. In such perspective, they want to have a benefit from their “tax investment”. This basically what DFID defines as patronage and leads straight to kleptocracy.

In South Sudan, there is an interesting experiment that is being done: the central state wants to empower the traditional chiefs to distribute justice and police. I personally have nothing against but I cannot avoid seeing it as a redo of what was done in the 70th by most of the African governments. Mobutu was extremely good at it.
The main problem being that by empowering local traditional leaders, the central state skip its responsibility to administrate its territory. It builds artificially a distance between the modern administration and the people, allows the modern administration to be only a tax collector tool which actually does not deliver anything except sanctions if the taxes are not paid. Basically sets all the bases for any insurgency or reject of modern state and discredit all efforts do have good/responsible governance.
I must say that I do not know were the response is but at least, I see many of the walls…

The Curmudgeon:
I agree. I am not sure where this is taking us, but I like "self-determination" a lot better than state building.
Curmudgeon,

Could you please define self determination? I am in one of those exercise at the moment and it’s quite creepy actually.