Ah, so many options!
The motors will run on 3 LiPos? Why not do that then.
Then get one of the stepdown regulators from pololu.com (on sale this weekend?) to make ~3.9-5V for the arduino.
Pololu Adjustable Step-Up/Step-Down Voltage Regulator S8V3A
Get some resistors & a couple of relays or analog switches (like DG406, search around at maxim-ic.com) to make voltage dividers so you can connect the 3.7V, the 7.4v (ex two 5Ks, measure the middle), and the 11.1V (ex 3 5Ks, measure across the bottom one) to the ADC to make measurements and deduce what ever you can.
Put in some MOSFET switches so you can disconnect the motors from power via under s/w control.
Autoshutoff - software issue to deal with after you get the other stuff going. Have another voltage divider driving an input when, monitor the pin, when it gets dragged low then call it quits.