Well a powerful 12V battery would do those motors (or even a 3S LiPo pack, which is nominally 11.1V). If its capable of sourcing enough current so it never overloads then you can run some 5V regulators from it too to give the servo and Arduino supplies. I'd suggest separating the servo and Arduino supplies as servos can pull brief large currents and pull-down the supply.
If you use a (brushed) RC motor-controller(s) it(they) will typically have a 5 or 6V output for powering servos too, and be quite compact. RC motor controllers for RC cars/trucks with brushed motors are the ones to go for as they have a reverse capability.
Alternatively some motor shield or motor driver board for you motors from the 12V supply.
You'll have to work out how much current your setup is going to use (both average and peak) to start selecting power sources.
Fitting a fuse in the battery line is a good idea