You could trim off the power, since presumably the device is internally powered anyway. (Of course the progammer would then need its own power, eg. a battery).
end users would not require any extra hardware ...
Apart from an audio player and some wires? And an interface circuit?
You could make a dedicated ICSP programmer (eg. in a small box with a battery). Load the new code into it in program memory (like my bootloader programmer described here), tell the user to shove in the wire you described, and hit the "program" button, and wait until an LED changes colour (a second later).
The programmer itself would only need to be an Atmega328 (or similar) chip, a couple of capacitors, a resonator, a couple of resistors and LEDs, the box and a switch. Should be able to make it for $20. And you could have a similar socket in the programmer for reprogramming it (with the new firmware).
I'm pretty sure there are commercial devices that do just that, I remember CrossRoads was talking about getting one.