The LiPo battery has a small self-discharge, and contains a lot of energy. A LiPo battery would be my first choice. Discharging them too much could be a safety risk, so if you don't trust the electronics and the environment you could use a few closed/sealed lead gel batteries. Submarines used to have lead batteries.
A LiPo battery is between 3.0V (or a little higher) and 4.2V. The 3.0V is not enough to run a normal Arduino. So you could use a boost converter.
But you could also run the ATmega32U4 (the microcontroller in the Arduino Leonardo and Arduino Micro) from a LiPo battery. It runs even at 2.7V at 8Mhz. For example the LilyPadUSB board is an ATmega32U4 at 8MHz. So you could use that board or make a compatible board yourself.
LilyPad USB: LilyPad Arduino USB - ATmega32U4 Board - DEV-12049 - SparkFun Electronics
Take a look at this, that seems just what you need, USB / DC / Solar Lithium Ion/Polymer charger [Rev C] : ID 390 : $17.50 : Adafruit Industries, Unique & fun DIY electronics and kits
A stepper motor and a brushless motor don't have the contacts inside that could corrode.
Perhaps you need a brushless motor with a gear.
I found this movie:
