If you want to get sixteen linear brightness levels, and if either your PWM rate is high enough or you don't need to change lights' brightness levels too often, you can get by only sending four updates per frame. The trick is to send a frame of data which will output for 8/15 of a "PWM interval", a frame which will be output for 4/15, a frame which will be output for 2/15, and one which will be output for 1/15.
If sending two frames of data separated by only 1/15 of a PWM interval would be difficult, one could use the output-enable control signal to shorten the length of time that the 'short' frame is output. In a somewhat extreme version of such a scenario, one could send out one frame for 8/32 of a PWM interval with the output enabled the whole time, one frame form 8/32 of a PWM interval with the output enabled for half of that (i.e. 4/32 of the entire interval), one frame for 8/32 with the output enabled for a quarter (2/32), and one for 8/32 with the output enabled for an eighth (1/32). This would mean that even at maximum brightness the output would only be on about half the time, but the output shift rate would be uniform. One probably wouldn't want to push things quite that far in the direction of uniform frame rate, but one could easily formulate other patterns which would trade off maximum shift rate for maximum duty cycle.
Another alternative would be to use four sets of 74HC595's, and arrange for some logic to have one of them output half the time, one of them output a quarter of the time (while the first was idle), one output an eighth of the time (while the first two were idle), and one a sixteenth (while all three of the above were idle).
In any of these methods, it's important to note that updating the brightness setting of an LED may cause it to momentarily be slightly brighter or dimmer than it should, especially between consecutive settings in which many bits flip (e.g. going from 7--0111 to 8--1000). This effect may be minimized by splitting the time interval associated with the more significant bits into multiple smaller pieces, but such splitting may be more readily accomplished in hardware than in software. If one can't afford a "pure hardware" solution, however, one may be able to use a hybrid solution (e.g. two 595's per bit; one gets loaded once per 'frame' with the MSB of the brightness, while the other gets loaded multiple times per frame, with the othe bits). Using two 595's would cut by half the required data update rate; using three 595's would cut the update rate by a factor of four. Using four 595's for 16 levels of brightness would cut the required update rate to zero (since hardware could maintain the "pwm" automatically).