Getting past the fact that the 555 won't supply enough voltage, ever, the next question is how can we amplify it. The answer is with a transistor. It took me way longer than it should have to get it to work, because of wiring problems and cooked transistors.
First the wiring: instead of taking 555 Output Pin 3 to the + side of the relay coil, I connected it to the base pin of a 2N2222A transistor (NPN BJT). I then connected + side the relay coil to the 5V rail, and the - side of the coil to the collector pin of the transistor. The emitter pin goes to GND. Initially, I left the LED in the circuit, but since that's connected to GND, the circuit was always completed. I'm sure there's a place I can put it, but it works without it.
After few wrong connections, I still could not get it to work. I was absolutely sure that it was wired correctly. During this process I must have cooked a transistor or two, In desperation, I replaced the transistor again, and it worked.
So, that's the answer: insert a transistor, properly wired, and the voltage that was too low to trip the relay is enough to activate the transistor, allowing 5V to flow from the 5V rail through the relay to the collector, and when the 555 is triggered, the output pin will supply enough voltage to the base pin of the transistor to allow current to flow through to the emitter, completing the circuit.
Here's the video
I'm glad I got this to work. I hate to leave something incomplete..