How to shut off a valve safely in the power outage
A supercapacitor or a small battery should provide adequate energy storage.  Most supercapacitors have too great of an internal resistance, but some low ESR devices are available, e.g. something from the AVX BestCap range.  A 100 mF device ($11 USD) would drop from 5 V to 4.5 V after a 0.5 A, 100 ms discharge.  If that final voltage is too low, you could use a 200 mF supercap (I would not recommend charging the capacitor greater than 5.0 V, since its rated voltage is only 5.5 V).

You'll obviously need a switching device (e.g. power MOSFET) and logic to detect the power failure and enable the FET to supply power to the valve.

If this sounds too complex and expensive, and you can accept a greater current draw when the system is normally powered, perhaps you could use a spring-loaded normally-closed valve that has to be held open with power.  To make the consumption (and heating) less egregious, you can use a special circuit that uses a higher current to move the valve and a lower current to hold it open.  TI even makes an IC just for that purpose.