How do you figure out an efficient battery setup?
and the arduino wastes current like a madman


what do you mean by this? I suspect it consumes about 25 mA. And also I suspect your motors take far more.

So with 2500 mA*h accumulators your arduino should work for about 100 hours. However I could not say anything definite about your motors since you keep their parameters in secret :)


  apparently 9V have very low current 


what it is about? do you mean some particular 9V battery? the principle is rather simple here - the larger battery have the larger store of energy.


  without buying more chips?


No chips will create you additional energy from nothing. So basically you check the current of motors, multiply by hours you want them to work - and you got the capacity parameter for batteries...