Problem solved, had to look deeper into avrdude options (type avrdude in Terminal) and found out that I can write directly to the fuse registers provided that I know what to write. Which leads to...
This handy life-saver calculator whose link appears at the bottom of the SoR calculators page:
http://www.engbedded.com/fusecalc/Hopefully it won't be going anywhere anytime soon.
So the full command ended up being: avrdude -c usbtiny -p m8 -U lfuse:w:0xe4:m -U hfuse:w:0xd9:m
No errors from the programmer, and the robot still runs.