Technically, you can make a single color 8x8 matrix without any ics. You use 16 arduino pins, 8 resistors, and 64 LEDs. I've made a 64 LED cube (4x4x4) with 64 LEDs, 4 resistors (16 resistors works better), wire, solder, and an arduino.
You can also do this with charliplexing, You could even do this with RGB LEDs if you use charlieplexing. Check out asher glicks charliecube. http://aglick.com/charliecube.html
Im working on doing some documentation for this, he shows you what you need to accomplish, but not so much about how to get there, and its a bit tricky.
Technically, this design should be doing damage to something Im unclear on weather its the LEDs or microcontriller at risk, but I've been running them over a month, without failure, and no appreciable differences in brightness or color, or speed.
If you really want to use shift registers, then you should check out ShiftPWM:http://www.elcojacobs.com/using-shiftpwm-to-control-rgb-leds-with-arduino/
I made a few examples that ran straight off the arduinos 5v pin, plugged into a 5v USB phone charger (about 500mA), I only ran them for a couple days, and technically its probably too much current for the arduino, so it *may* be doing some kind of damage.
Have you considered constant current drivers? They make chips just for controlling many LEDs, it makes things a lot easier, less stuff to deal with, less stuff to screw up, and tidier too.
If you want more examples of people using multiplexing with transistors, also check out cubes, and LED strips.
Here Ladyada is using Mosfets and Darlingtons to power strips.http://learn.adafruit.com/rgb-led-strips/usage
Im still trying to figure out sinking and sourcing to my 2 other cube setups (one with shift registers, one with constant current driver), but I've been busy with other things. The charliecube was a lot of work soldering, but I had it working within a week, my other cubes are still not finished, and I started them over a month ago.