IDK if you've looked into batteries yet, but for maximum power density (you know, that you can actually buy) and the best cost per Wh, check out the LiPo available at hobbyking.com. IDK how much capacity you'd need, but one (or multiple) of these should do the trick nicely (ignore the 11.1V nominal; LiPo cells are happiest between 3.8V and 4.2V per cell and have a pretty flat discharge curve, so these packs should stay pretty close to 12V for most of their discharge cycle).
5Ah :
http://www.hobbyking.com/hobbyking/s...idProduct=9184
8Ah :
http://www.hobbyking.com/hobbyking/s...dProduct=16225
(btw, a tip, if you decide to buy from hobbyking, let the webpage sit at the product you want; it'll frequently eventually pop up a little thing in-window offering a lower price)
For context, your standard UPS battery is a 12V 7Ah SLA.