I find myself wondering what exactly differentiates a "government" from a "family council" or "tribal leadership" or whatever other phrase you want to use to describe an "authority-wielding-body with a monopoly on force."
I think "governments" are as old as people, and probably older. Many social animals have leaders who dominate the rest of the herd.
My feeling is that governments have always been here, they've just gotten bigger and maybe a little more sinister.