This is an interesting project you have here. I hope you can share the results with us when it is finished.
While that LED will work, you will definately get higher output for the same amount of energy consumed using one of the new high efficiency LEDs, namely Cree or Seoul. Direct driven with a 5 Ohm resistor (yes they make them in 1/2 Watt) would limit the current a bit more than in your calculations, so you might want to use three 1 Ohm resistors in series.
Multiple capacitors would be connected in parallel to increase capacitance. Of course, most capacitors don't hold a charge for very long, so realize that the user of the device would have to recharge it if it sat for long. As far as what type of capacitor to use, that depends on how much energy you want to be able to store. You definately would want to find a capacitor with a high capacitance and a voltage limit not much above your input voltage. The reason for this is that a capacitor with a high voltage capability will have a lower capacitance for a given size because to sustain a higher voltage requires a thicker dielectric (or a better one).
If you can afford them, the new ultracapacitors would give you the best energy storage capacity among capacitor choices. NessCap makes a 5.4V, 2.5 Farad capacitor selling for about $6 ea. That will store 11.25 Coulombs of charge at 4.5V. As the capacitor discharges, the voltage available to drive the circuit decreases exponentially, so while it will start out driving the LED to spec, the LED current and light output will die down. How quickly? Well, after about 32 seconds (the time constant for this circuit) there will be only 7 Coulombs of charge left in the capacitor, which will be able to apply 2.8V to the circuit. This will still drive the LED at about 220 mA. At 64 seconds, you only have 1.7 Volts driving the LED at 130 mA. You could gang a bunch of these capacitors in parallel to increase runtime, but this is not a very good solution IMHO.
So, while you could use a capacitor for this application, you only get a couple of minutes of usable light. I think a better way to store energy in this application is with a NiMH battery. The circuit needs to charge the battery at a rate not to exceed specifications (depends on the battery size) and is then free to discharge it at a much more consistent voltage. You will also be able to store more energy per unit volume and at a lower cost than if using capacitors. Capacitors have an advantage when you need to extract the stored energy quickly, but this application does not require it.
Edit: Actually, you would want to use 3 NiMH batteries in series, not just one. Furthermore, a protected Li-ion rechargeable might be an even better choice, since you wouldn't have to worry about over discharge as much due to the built in protection. But, NiMH is more tolerant of overcharging, so each has its advantage. If choosing Li-ion, I recommend AW's protected batteries. You will want to avoid charging them beyond 4.2 V.