Hi capacity NiMH cells (AA or bigger, prob not AAA), LiPo cells, SLA batteries, High current alkaline's (again AA or bigger). All depends on the motor current draw.
The key thing is not to power motors directly from the same supply as delicate electronics. Say your motor supply was 12V and the motors were not too chunky to pull that voltage below 7V ever, then you could use the supply for the motors and for Vin, using the on-board regulator to protect the Arduino from the supply voltage noise/spikes - but even then I would recommend more decoupling capacitance to limit high voltage spikes.
Actually there are big 9V batteries available (PP6 and PP9) but they are hard to find - very old transistor radios used to use them. Nearly all 9V batteries these days are PP3s - good for 50mA or so, not amps.