They didn't necessarily need gold. For example in bronze/iron age trading it was common to use relatively standardized small bars of other metals for payment. These were not coins, but approximately had the same function.