I completed a project like this a few years ago for a 120x7 LED sign with a dead controller. To do this, I wired the sign as a 28 anode/30 cathode array and designed a controller that would refresh a 32x32 LED array.
The main "guts" were:
- four ST STP08CL596 IC's sinking current from the 32 array cathode lines.
- four ST STP08CL596 IC's sinking current from the bases of 32 MPS751 PNP transistors, to enable individual anode lines.
- an ATMega8L, later a Mega168, doing control duty.
The eight STP parts were connected in series and connected to the AVR SPI port, and the /OE pin was driven by one of the AVR timers. I used the 8MHz internal RC oscillator on the AVR, SPI frequency was 2MHz, and the scan ("next anode") frequency was 2400Hz yielding a 75Hz overall sign refresh rate. It took up surprisingly little CPU time on the AVR.
The AVR emulated a 20x1 serial HD44780 LCD, custom characters and all. Worked great with Winamp.
If you're going "big" (500+ LEDs) then an implementation like this might be what you're after. I'll post design/schematics/pictures/etc if anyone's interested.