Well I can think of several descriptive terms which meet what you are describing but which do not invoke the term "government", which, despite the etymological history of the word, is by now irredeemably linked with the State.
dispute resolution organization
adjudication agency
defense and justice association
insurer
Just to name a few.
I believe that in a free market world, such firms would become dominant, through market forces, in their respective areas (as you have described), but not to the extent that they become territorial monopolies. Each of these firms would produce the service known as "laws" or "civil order" or a "code of conduct" by which people would, out of economic necessity, tend to live. But a subscriber to one would by no means need to renounce it when he goes into a different region; rather, there would be adjudicators specializing in conflicts between parties of different legal systems.
And although some of these bodies of law may be statelike in nature, the lack of a territorial monopoly would relegate their enforcement to the fringes of society, along with the enforcement of arbitrary and otherwise inefficient systems of dispute resolution. This does not mean that the prevailing legal order would be a default monopoly, as several efficient and fair systems could coexist in the same area, but those systems which exist on the fringes may be excluded from a particular geographic area by default.
E.g., Sharia law may be used to resolve disputes, but in most areas, the enforcement of Sharia law would be excluded by the prevailing legal doctrines. Hence, fundamentalist Muslims would be able to obtain a ruling on a case no matter where their dispute occurred, but they would have to seek out a geographical area wherein such enforcement would be permitted.