I'd use the 5v REED relay (RS # 275-232) I don't think 9 volts would hurt it because the TLC 555 pin 3 actually don't send the full battery volts to the relay, probably only 7 volts really gets to the relay.
The REED relays use a LOT less current than the blue ones (it only uses about the same amount of power as the LED's ! ! !
If the relay won't pull in (close) need to double check your wiring, it gets kind of tricky at the switch/LED part.....
The Protection Diode at the relay should have the banded end toward pin 3