Quick answer with some assumptions.

Assuming a 100Ω solenoid, one would draw 120 mA current on 12 V DC. (12 / 100 = 0.12) 

36 solenoids would use 4.32 A. ( 0.12 * 36 = 4.32)

A 12V 7 Ah sealed lead acid battery (This size is moderately portable and easily available) would last a over an hour at this load.

7 Ah = 1 A for 7 hours = 7 A for 1 hour = 3.5 A for 2 hours.
(This is a simplified calculation for ampere-hours. Practically, the capacity goes down with increased load current. A battery that gives 1 A for 7 hours will be able to source 7 A for less than an hour)

For 4.32 A, 7 Ah would run for 7/4.32 = 1.62 hours.

This doesn't take into account the switching losses or the duty cycle of the solenoids. If you turn on only a few solenoids at a time and have them turned on only for short duration, you can expect a lot more run time.

If you want more run time, try a car battery which at around 35 Ah would give you more than 8 hours run time.