Per definition, you need a government to have insurgents. The fact that the government is or not legitimate does not really matter.
In failed states, governing by abandonning part of the State supremacy to local war lords can and has been a form of government in failed states. In such cases, it is difficult to really establish if government is representing the whole State or just the formal form of administration that a modern state can discuss with.
But even in non state environment, such as Somalia, you do have a form of government. The main issue is that it is not unified, does not correspond to our form of governance... Therefore each and every little agreement has to be negociated with each and every war lord. I like to picture it as an archepelago of small state like organisations in a sea of sand...
If you want to impose a webberian modern state on them, I am not that sure that you need COIN in the first place. At least not pop centric COIN.
You need to establish the military suprematy of the government you do support first. That needs to be violent and unflexible.
Then, in the area where you have control on you can think about pop centric COIN as a magnet to rally populations to your side. But they will rally just because your the strongest, mightest and they fear you, not for any other reasons. The social services and formal state administration will just a cherry on the top of the cake.