AVR AtTiny84 is stuck on 128kHz clock, avrdude + Arduino as ISP can't reach it
OK - I found a version of the ArduinoISP sketch that supports a slow-speed option for the SPI programming:

https://github.com/adafruit/ArduinoISP/blob/master/ArduinoISP.ino

By defining the LOW_SPEED macro I was able to reprogram the fuse bits to the default 1 MHz. So problem solved.