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,
Roman (EEEngineer)