You will have to use another, higher voltage power supply with your own regulation to reach the stage before the 5V. I used 9V. (this might solve the issue by itself without the giant cap)
The phenomenon we are experiencing resets the Arduino without letting it run any setup code it seems. You need to enable the WDT in hardware so that it is always on by setting the WDTON fuse setting on the ATmega328. You will need an ISP programmer like the AVR ISP mkII for this (preferred) or you can use another Arduino, but the ISP programmer is much cleaner and quicker. After you find your programmer, you can either use the Atmel Studio 6 "Device Programming" panel or just command-line avrdude (quicker but easier to brick your chip). Then the WDT will always be on for I believe 64ms, which you can change in the first line of your setup and throughout your program.