Hi again Joe,
When i finally figured out how the circuit should be I came to see that you answared with the circuit I thought it should be.
It should be quite easy then.
For this solenoid, nominal current should be 12V/15.6
= 0.76A approximately the 0.75A floobydust said.
With this circuit it will only draw about 0.58A, so it won't work full force, perhaps it won't have enough strength to pull/push the plunger. But i think it will be sufficcient as long the plunger don't need to use a lot of force. Just test it out.
As I see your main problem is the battery, batteries also have a limitation with the amount of current it can supply at once. So even if your battery has 500mAh capacity, it could be limited to supply 750mA at maximum without damaging it (These values are random, just for example).
Now, for the capacitor, as Floobydust said you will have to use big capacitors.
As I said, the solenoid can be viewed as a resistance (so the inductance value won't matter here). The time for a capacitor charges/discharge is called RC time constant, and as the name says it's a simple multiplication of R x C. RC is the time it takes to charge/discharge 63% of it's power.
So let's say you want the solenoid to be active for 100ms, you will need a RC time bigger than 100ms. It's not a linear charge/discharge so it's hard to get an absolute value. Try use RC = 500ms, this should give you 100ms with voltage of 9V to 7.2V (See capacitor charging/discharging graph).
For the equation: RC
time = R x C therefore C = RC
time/R = 500m/15.6 = 32mF or 32,000 uF. Crazy big capacitors and quite expansive ones (probably using 3 10,000uF in parallel should be cheaper).
Sorry for the long awnser, or if it's confusing (english is not my first language), but i wished to explain the details so you will know how it works properly.