>Some kinds of money surely existed before anything recognizable as a "state"

I wouldn't be so sure. As far as I know, current academic consensus is that in primitive societies, where everyone knows everyone, it comes down to a system of favors and everyones natural sense of what's "fair". These are relatively small groups of people, so there's a lot of trust involved. No need for any sort of currency there