One example that should be easy for your statist coworker to understand is Visa/Mastercard. Those are not issued by any government, yet are more universally accepted than any fiat currency.
A replacement for government money could be notes bearing either the Visa or Mastercard (or, of course, any other generally-acceptable firm) logo, and indicating a fixed quantity of gold into which the note is convertible upon demand.
In practice, just like today, most transactions will be conducted electronically.