Looks like I'm gonna keep this thread alive even if it kills me!

My friendly neighbourhood parts guy didn't have any of the high current TPIC6B595s. But thankfully, he finally got the 74HC595s and it has made a world of a difference over the HCF4094Bs.
One curious thing to note. Initially I had the same problem as earlier where the rows were bright and columns weren't. But when I changed the orientation by 90 degrees (in the code I mean), it suddenly looks great. All LEDs are of more or less equal brightness.
Couple of things to note. I switched from using shiftOut to SPI and wow! The speed has increased by more than 10 times. Secondly, I got some pretty 8x8 bit fonts from
Richard Prinz's Pixel ROM Font Editor. It has a whole bunch of pre-built fonts from the C64, Macintosh era.