Can you tell me where in my diagram to put the decoupling capacitors?

Put a ceramic 0.1uF and 10uF, or larger, electrolytic across the power pins of the 555 timer.

For the circuit on the right, what would be the way to fix it?

To prevent junction breakdown, put some signal diodes anti-parallel to the base-emitter junctions. If the off LED lights dimly, you can try putting a 1k resistor in parallel with them. A better solution is to use N channel MOSFETs instead, so you won't have base current going through the off LED. Or have the transistors turn the LEDs off instead of turning them on.

EDIT: add schematic showing first and last suggestions

 

Thanks Dennis, I will test this out (but I have to re-build it on my breadboard). I've never played with an N-channel MOSFET, would swapping it in my circuit be a matter of replacing the transistors and Base=Gate, Collector=Source, Emitter=Drain?
would you have a part # I can use as a reference?

 

I've never played with an N-channel MOSFET, would swapping it in my circuit be a matter of replacing the transistors and Base=Gate, Collector=Source, Emitter=Drain?
would you have a part # I can use as a reference?

2N7000 are probably a dime each in quantity 100. They're easily damaged if not handled properly.

You have the source and drain connections reversed. Frequency of oscillation will be lower because the MOSFETs require a higher turn on voltage.