UPDATE 12/2014: I've posted a simpler circuit.

I've tested this circuit. The LED brightness is now awesome. LEDs are getting almost 10ma even when pulsed.
However, it seems like an unnecesarily complicated circuit. Any thoughts on making it simpler?

The transistor driving the MOSFET gate is necessary because 5V from the Arduino weren't sufficient to drive the gate.

64 more transistors are necessary to drive the LED cathodes because without them, the LEDs were always on regardless of the bit value on the shift register output. When the bit is low, the LED is brighter, when the bit is high (5V), the LED is dim, but not off. I think it's because there's still 4V difference between the LED cathode and anodes.