> I'm not sure how much value money would have without a government to back it up.

You don't need a government backed paper currency, you need a mint making precious metal coins. History has several examples like the mints at the Potosí silver mines or those by the East India Company that enabled trade without effective governments to back them up by just providing reliable coinage that spread to many other polities.

As long as there isn't some crazy inflationary force like colonizers arriving with an unlimited supply, we can use something as simple as beads or seashells for currency quite fine. It just means more labor overhead to create that currency in the first place.

doesn't even have to be coins

Somalia operated on paper money valued at the cost of producing it