You've conceded that in absence of a government, people have the right to enforce their own personal justice. If the right to pursue justice still exists in absence of a government, then some sort of law must also exist in absence of a government (from what else would you derive a right to seek personal justice?) The laws to which I appeal now do not come from governments, books, or gods; I believe they are encoded in our genes after eons as living as a social species. Social instincts which evolved to facilitate cooperation in groups are the root of all basic laws written down by governments. When somebody is wronged, in violation of these universal laws, they feel it in their bones.
If you don't believe any of that, believe this: when people feel wronged they will seek justice. Either a government can provide them with a safe framework to receive justice, or people will seek it themselves. You'll never succeed in scolding people away from desiring justice. When seeking vigilante justice is routine, that is categorically a failure of government to provide justice.