What crossroads says is pretty accurate. Basically what he is saying is that using parts that meet or exceed your needs will reduce your chance of premature failure. You could get away with 595s, they wont break right away, but your needs exceeds the parts specifications, and may cause premature failure, and its not the proper way of doing things.
There are actually a lot of ways to solve this problem. I do like your idea of controlling 5 LEDs at a time, and doing that in a loop of 5 that is inside another loop of 5, and you have controlled all 125 LEDs. I dont think that I have seen that one before. It will have an extremely low duty cycle, so It will probably end up very dim, which is probably why we dont see that technique being used. It also means electrically isolating rows, which maybe tricky to make the structure hold up. its still an interesting idea, and may be worth playing around with.
If you limit the current to 8ma to your LEDs with resistors, you could reduce the current to the diodes to 8ma, then you would be within the 70ma max current spec of the 595s, and well within the LEDs specifications.
Another option is to simply run the LEDs and shift registers over spec, and expect to replace them sometime i the future, it can take months to wreck your leds or shift registers. You could build a spare in that time, and have it ready if this one fails.