For the battery backup you might want to think about something like the SparkFun LiPower shield.
It's a Lithium Ion / Lithium Polymer battery charge controller for the Arduino, so you can power your system of nice high power Lithium batteries and safely manage the charging of them.
You will need a regulated 5V power supply for it though, so in stead of a 12V wall wart, you might want to think about a 5V phone charger instead.