Running LED dot matrix using shift registers
You don't say which 74595 you're using. On the 74HC595 datasheet I have, the maximum current from Vcc or Ground is 70mA. 

So the Arduino's 500mA is not the problem. It is the total current handling capacity of the 74595's.

I'm assuming there is one 74595 for each 'column' of each colour, and one 74595 for the LED's common 'row'; it really doesn't matter if this is reversed, the issue is the same. 

Then the 74595 driving the common (anode or cathode) of the LEDs is the biggest current limit. You'd actually be slightly better off driving the commons with two different ports of the Arduino. Used that way, the Arduino could supply more current than the 74595 (about 40mA one pin only from a port.)

With your existing wiring, you need to use resistors on all 16 'columns' of LEDs so that the total current is less than 70mA. This means I = 70mA/16LEDs, say 4 mA per 'column'. This should still be visible, just not as bright as possible using two ports of the Arduino to drive the LED commons.

Edit:
For an 8x8 Red and Green LED display, the current limiting dimension is the one with the most LEDs connected to it. So, if there are 16 LEDs connected to a row then drive that with the best driver you've got, i.e. an Arduino pin.

I'd probably replace the 74HC595 driving the LEDs common with a 'power' version of the part, for example a TPIC6595 (search the web for "high power 595 shift register", many manufacturers make an equivalent), and drive the row/column with the common 16 LEDs with that. 

Alternatively, drive only one colour of LED at a time, so that the common row/column only needs to supply 1/2 the current. This would have a loss of brightness, but, if you've soldered everything together (and didn't use sockets), this should allow you to reduce the load on the shift register which is driving the common LEDs.