Here is a possible mechanism for the fault. You say it works (dimly) without the transistors, but doesn't work with them. So it sounds like the fault is in the transistors. Is there some reason that the transistors might be letting some current through when they shouldn't?
Yes. You're using a PNP transistor. As you know, these transistors are on when the base voltage is lower than the collectoremitter voltage. They are off when the base voltage is higher than or equal to the collectoremitter voltage.
The problem with the shift register chip is that the outputs are always lower than the collectoremitter voltage. I couldn't quite make out the part number of the chip you're using, but according to the datasheet for the 74HC595 (page 6), the outputs don't quite reach Vcc. If there is a tiny voltage difference, then you could find that a small amount of current is leaking out of the base of the PNP transistor. With a gain of about 100, you could find that there's enough CE current to give noticeable light output on the LEDs.
Something to try: Add a schottky diode between Vcc and the collectoremitter. This should drop the collector voltage by a fraction of a volt, just enough to allow the shift register to fully turn off the transistor.