The Maxim MAX7219 works with common cathode displays and uses a 3wire serial interface.
Or you could use a MAX6951 charlieplexed chip with SPI interface, this chip is only available in a small 16/QSOP package though - good for space saving if you can solder it.
I don't know if I can help in any way but we did a digital chess clock last time, and for the display we had eight 7-segment display (like microwave displays, the red ones).
Ours were common anodes so we had the motorola BCD to 7-segment decoder/driver or simply 74LS47...We used the pic 16f84 as the microcontroller...just surf for the specs of this IC