Problem with 7-segment display: dimly lit when off

You should be able to drive this very easily with nothing but the Arduino mega and 8 resistors, so you don't necessarily need 24(!) shift registers. You won't be driving all of them at once, you'll be driving one of them at a time. But it will be the simplest to build and take no extra chips. In all you'll probably need 32 of your pins, but the mega has no shortage of pins.

Remember that each of the IO pins are tristate. Putting them into input mode puts them into high impedance mode, which is like putting a very high value resistor on that pin, essentially removing its effect from the circuit. By wiring each of the common cathode pins to IO pins and setting all of them to input, you can then set single pins to output low (connecting it to ground) and drive single digits at a time. Then all you need is a timer and cycle through each of the digits.

The only thing to consider here is how much current you're sourcing and sinking through the MCU. But for only 8 LEDs at a time, I think it should be OK, depending on how much current they like and what else you're powering with the MCU. I tend to go for designs with less external components, so this is the solution that appeals to me.

Also, the others are right in saying that a single current limiting resistor on the cathode is not sufficient. Your brightness problem is either related to this, or the amount of current your shift registers can source.

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 emitter voltage. They are off when the base voltage is higher than or equal to the emitter voltage.

The problem with the shift register chip is that the outputs are always lower than the emitter 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 emitter. 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.