Standalone Atmega 2560 ISP program
I have a sketch that programs bootloaders. A side-effect of that sketch is it fixes up the "divide clock by 8" fuse.

It looks like the wiring will be the same, but cross-check on that page (scroll down to the part about programming the Mega2560).

Once a bootloader is installed you could use it, if you get an FTDI cable, or simply go back to using the ArduinoISP now that the fuse is fixed.