The reason I'm doing this is because the relay is going to be dealing with a very high ac voltage and I'm trying to keep the arduino as safe as possible - also the relay may need its own power source.
In other words, is replacing the LEDs in this circuit with a 120v rated relay feasible?
If you want to switch 120vAC and your level of expertise is low then the following relay shield, or similar, is recommended - actually if your level is low then steer clear of mains voltage until you've developed some skill. http://www.robotshop.com/seeedstudio-arduino-relay-shield.html
Note that this is only rated for 360VA.
A well designed mains-relay shield will keep all the relay contacts well separated from the relay coil connections (about a cm is good), preferably with a plastic sheet on the underside to protect the traces from touching anything accidentally.
With significant power being switched, I recommend getting the relay(s) physically away from Arduino (Close to the load if possible), and using Optical Isolation so you don't need any direct electrical connection between Arduino and the relay circuitry.
See the schematic diagram on this page: http://goo.gl/PcWJ2 You could do something like this yourself, or buy relay boards. (The one shown is only $4)..
To be honest a relay would work providing A. it's rated for the voltage. B. it's located away from your breadboard C. there's a protective diode to protect the arduino board...
BUT
your led's are going quite fast it will wear out the contacts fast as the voltage arcs as the relay makes contact.
if you wish to keep that speed up and not worry about replacing all the relays every few months invest in solid state relays.
The light now works with a 5vdc relay switch rated for 120vac connected to the arduino. This is just a proof of concept and will be updating the code to increase the delay between switches.
Your relay will work, assuming that a) it is rated for 5v drive, and b) you have a free-wheeling diode on the relay; and c) your transistor is rated as such.
You may also consider a solid state switch for high frequencies or life.