All right. I finally a) wasn't feeling completely like death warmed over after dealing with whatever respiratory bug for the past month that's been going around and just will not go away and b) had a couple of hours with nothing to do after being out hiking all afternoon. So I dove into this.
I sat down and wired myself up an Uno R3 to be a programmer for Nick Gammon's Atmega_Hex_Uploader_Fixed_Filename sketch.
I used an USBtinyISP to program the fuses in a 328P like they come from the factory.
I compiled a simple blink sketch with the clock set to 1MHz internal, and used the USBtinyISP to upload it to the 328P whose fuses I'd set for 1MHz internal.
Took that 328P, stuck it in a breadboard, and it blinked at the 1Hz frequency I'd expected. Great.
Compiled that same blink sketch with the clock set to 16MHz external. Renamed the .hex file to firmware.hex, copied that to a uSD card and put it in the uSD adapter in the Gammon programmer.
Put the 328P in the Gammon programmer, powered it up, and used it to program the blink sketch compiled for 16MHz into the 328P with its fuses set for 1MHz.
Put the 328P back in the breadboard, added a 16MHz crystal and 2x22pF caps (even though none of that was needed yet), and applied power. As expected, the LED blinked 16x slower. Glacial, in fact.
Here's where we finally get to the good stuff.
I opened up the Atmega_Hex_Uploader_Fixed_Filename sketch again and found the updateFuses routine. At the end we see this:
if (writeIt)
{
writeFuse (fuses [fusenumber], fuseCommands [fusenumber]);
}
return false;
} // end of updateFuses
whose sole purpose in life is to unprogram the BOOTRST fuse if needed.
Taking the quick and dirty road to a solution, I modified this bit to this:
if( writeIt ) {
if( currentSignature.sig[0] == 0x1E && currentSignature.sig[1] == 0x95 && currentSignature.sig[2] == 0x0F ) {
// set 328P to 16MHz external
writeFuse(0xF7, fuseCommands[lowFuse]);
writeFuse(0xD7, fuseCommands[highFuse]);
writeFuse(0xFD, fuseCommands[extFuse]);
} else {
writeFuse(fuses[fusenumber], fuseCommands[fusenumber]);
}
}
return false;
} // end of updateFuses
Now, if we're programming a 328P, it sets the fuses to change the clock to 16MHz external. But only if we're programming a 328P; it works exactly the same for everything else. I could have gone through the sketch and stripped out everything for all other MCUs, but that seemed like too much work for an unpaid gig on a Saturday night. 
I uploaded the modified sketch to the Gammon programmer, removed the 328P from the breadboard and put it in the programmer, programmed it, and returned it to the breadboard. With power applied, the firmware.hex file, that was compiled for a 16MHz clock, that was uploaded to the 328P with the fuses set for 1MHz internal, just like out of the factory, had been uploaded to the 328P, and its fuses were set for 16MHz.
And the LED blinked at the expected 1Hz rate.
So there we have it. The Gammon fixed filename uploader hacked to set the 328P's fuses to 16MHz external.