The person in the video you linked (http://www.instructables.com/id/ThrobbingFading-LED-with-555-Timer/step6/Lets-Solder/) used a 9V battery to power the circuit. You can do that as well.
The limiting factor here is your 555 chip, it will need a minimal voltage to run correctly (and also a maximal voltage you cannot exceed).
By far the most common chip voltage supply input range from 4.5V to 16V. For example: http://www.ti.com/lit/ds/symlink/lm555.pdf
You can use any supply the can give the voltage in that range.
Remember that if you use a battery the "smaller" it is the shorter will be the running time of your design.
Take care, Source: I'm an EEEngineer