Of course i've not done this so i'm talking theoretically.
I have just been playing with a single 8X8 matrix multiplexed in software with the Arduino this weekend. No shift registers, column drivers straight off the data pins, row drivers from a demultiplexer (74LS42) so only 4 pins with direct port access. I am having to refresh at a rate of 2mS to stop any flickering.
2ms * 8 = 16mS per frame so about 60Hz, I am not confident about doing more.