Connecting three keytars to the NES
The NES controller contains a CD4021 shift register. This acts as a parallel-to-serial converter, with the parallel inputs connected to the buttons. You could use a CD4021, but connect the parallel inputs to output bits from the Arduino. This will relieve the Arduino of the high-speed clocked part of the problem.

If you cannot modify the keytars, then you are limited to either a MIDI (async serial) or USB host interface. You will, as you suggest, need a USB host shield or a MIDI shield. MIDI sounds a bit simpler to work with, given that it's basically a stream of serial data.

I can't comment on the bug that you mention (not an expert on the NES at that level).

I think your approach is along the right lines. Maybe start by getting the keytar-to-Arduino side of it working first. Also try out a CD4021 shift register and some buttons, i.e. build your own NES controller from scratch.