Hmm. And I think I just found half the answer to one of my problems. Here's a guide to controlling the exact same stepper motor controller board that I found on eBay, using Arduino:
http://www.utopiamechanicus.com/article/arduino-stepper-motor-setup-troubleshooting/
Is anyone familiar with the Arduino program the author references ("stepper_oneRevolution") and know whether it could be run on the ATtiny85 rather than Arduino? If so, that sounds like a possible solution to me: Each of the 64 ATtiny85s is connected to a ULN2003 driver board and runs a modified version of the "stepper_oneRevolution" program. Each ATtiny85 is programmed with its own unique 6-bit address number (0-63), and listens for 2-byte instructions over a common serial interface from the central Arduino. The first byte of info is the address, the following byte is a command to turn x number of revolutions in y direction, which the selected ATtiny85 translates into instructions for the ULN2003 board using the "stepper_oneRevolution" code.
I'm thinking out loud, ja?
Anyway. Sound reasonable?