Using a PWM Arduino output connected to the OE input of the '595 only allows you to fade all 8 LEDs together. You need to fade them independantly.
Have another look at that link groundfungus gave you. That will allow individual fading. It does use alot of the arduino's processing power to achieve it, but you may well not be using very much anyway, so not a problem.
Another option, as you suggest, would be an LED driver chip with individual fade control, like TLC5940.
Paul