The data sheet for that specific servo says it should definitely not be run at 9V; it is rated for 4.8-7.2V.
http://www.electronicoscaldas.com/datasheet/MG995_Tower-Pro.pdfYou will definitely not want a battery with a voltage over 7.2V, so I would recommend a 6.4V LiFePo4 pack (google Lithium Iron Phosphate). Ordinarily I'd stray from something like that, but only due to the dangers associated with Lithium battery packs. However, for running 12 servos and a micro controller, you're gonna need the energy density that LiPo can provide. Now we just have to figure out the current you'll need.
The data sheet doesn't specify what max current the Servos can take, but it does say that they are meant to run off of a variety of R/C receivers, all of which I know provide around 5V at usually 2A or less. However, they are usually meant to power multiple servos simultaneously, so I'm gonna take a guess and say each one needs a ballpark of 0.5 A. That means you need to supply up to maybe 6A at one time to power 12 of them. This is probably a bit low, but you will also rarely need all 12 moving at once at full speed, so it's probably a fair estimate.
On BatterySpace, the cheapest/smallest battery that could suit your needs is this:
http://www.batteryspace.com/LiFePO4-18650-Battery-6.4V-1200mAh-Flat-7.2Wh-10A-rate.aspxHowever, this would provide an absolutely pitiful run time. Assuming you use an average of 4A continuous current, not adjusted for inefficiency (which, let's face it, there will be a lot of with 12 of these guys either idling or running), you will have 1.2Ah / 4A * 60min/h = 18 minutes run time. You're getting just over a minute/$ on this battery. Let's see what else might work...
This battery has twice the storage capacity and is only $35, so it will provide 36 minutes of run time with the above estimate.
http://www.batteryspace.com/lifepo418650battery64v2400mahsquare144wh14aratewithpcbandpolyswitch.aspxThis battery seems like the best value:
http://www.batteryspace.com/custom-lifepo4-26650-battery-6-4v-13-2ah-flat-84wh-16a-rate-7-9.aspx At 13.2Ah it dwarfs the others, though it costs over twice as much as the last mentioned at $74.50, and as a large pack it'll probably be cumbersome to your robot and your shipping costs. I'd expect it would cost closer to $87 shipped. However, the run time you would be estimated to get is... wait for it..
198 minutes! Even after losses and powering many things besides just the servos, you'll likely get well over 2 full hours of use out of this thing on one charge.
Note well: you should never actually get 198 minutes from this guy without discharging it to a dangerous level, but 2 hours is very realistic and likely repeatable. I hope this helps you somewhat. Just keep in mind that without the proper charging equipment and maintenance, you can have a lot of problems with Lithium batteries, especially LiPos. My brother learned this the hard way when he had a LiPo charger malfunction, causing the battery to overcharge and eventually explode and burn a hole in his carpet, which fortunately was as far as it got before firefighters dealt with it. This is a very uncommon occurrence, but nevertheless, I cannot emphasize it enough:
Never leave a Lithium Polymer battery unattended while charging! There are very visible signs such as inflation of the cells and excessive heating that can give away a potential fire hazard before a disaster occurs. Also, in the event that your battery does fail, instructions indicate that you should never leave it unattended, and if you have, you will not have grounds for insurance to pay for the damages. I highly recommend you get a smart battery charger recommended by BatterySpace such as this one:
http://www.batteryspace.com/smartfastcharger12aforany64v2cells76vcut-offlifepo4batterypack.aspxIt's not even that expensive, and it is well worth it.
I hope this helps!
