replace battery with capacitor
Do the math.

Energy needed by the solenoid:
\$12 \text{V}\times 500\text{mA} \times 2\text{s} = 12\text{J}\$.

You can charge the cap to 12 V and a boost switcher will convert the cap's decreasing output voltage to 12 V.  Let's say the boost switcher is 80% efficient and can operate down to 2 V.  So the cap needs to provide \$\frac{12 \text{J}}{80\%} = 15 \text{J}\$. 

After discharging the cap from 12V to 2V there will be a fraction of the energy left: \$\frac{(2 \text{V})^2}{(12 \text{V})^2} = 0.028\$  

So the cap must hold a total energy of \$\frac{15 \text{J}}{1 - 0.028} = 15.5 \text{J}\$ at 12 V.  

The minimal capacity needed is: \$2\times \frac{15.5 \text{J}}{(12 \text{V})^2} = 215 \text{mF}\$

So, you need at least a 220 mF 16 V cap.  This assumes you have a boost converter that can produce 12 V at 500 mA from 2-12 V and is at least 80% efficient.