My assumption was that it usually comes down to finding someone else with money in both currencies (i.e. a large bank or government) and exchanging one for the other. Of course that's unsatisfying: it's not just turtles all the way down.
Ultimately if I'm running out of, say, USD, and have a lot of CAD, I have to to buy a bunch of something for CAD and sell it in USD. If you wanted a "zero banking" currency transaction I guess the way to do it is to park on the Canadian side of the border, buy imports to the US, walk across to the US, and sell them.
Or maybe there's a magic money shredding / printing machine that I didn't know about. I guess an international treaty could actually authorize such a thing.