You might want to try a 3 cell (3S - 11.1 volt, 3.7 volts per cell) LiPo RC pack - run the whole system from the single pack.
Get a Y-connector - hook it to the battery with a properly sized fuse (on the positive lead) between.
One branch of the Y-connector goes to your motors (with the motor shield in between of course); the other side should go to a 5-volt SBEC (battery eliminator circuit - get one that uses a switching regulator; some cheap ones don't - and supplies 2 amps or more).
Hook it's output to the 5 volt inputs on the Arduino and motor shield. That should take care of everything.
Some notes on LiPo's (do your research, too, before investing in them) - they are much lighter weight than other packs, and can supply a helluva lot of energy. Make sure you get a proper charger for the pack when you buy it; they need a quality charger that is meant for LiPo spec'd for the number of cells. Any other charger is likely a dangerous proposition. Even with a proper charger, charge the battery in either a LiPo fireproof bag, or inside the voids of a concrete block, set on concrete, with another block on top to close it off. The reason why is that these batteries can go into "thermal-runaway" when charging, and ultimately explode and/or catch fire. It's not common, but it does happen. A few RC modelers have had their houses destroyed because of one of two reasons: 1) they didn't take the safety precautions for handling/charging their batteries, and more importantly, 2) they didn't continuously monitor the charging of their batteries (always be on-site to monitor the charging of RC batteries, especially LiPos!).
If you decide not to use a LiPo battery, consider the same setup as above, but use a 8-10 cell NiMH battery. Even standard 8-cell 9.6 volt NiMH batteries should run your motors OK.
Finally - regarding that motor shield (and this will probably affect the needed number of cells in the battery) - first, the L293 shield may be too small for your motors; they can only supply a maximum of 1 amp per channel (or 2 amps for both channels); in reality, you are actually looking at about 800 mA per channel (and even then, you'll need beefy heatsinks). An L298 based controller would be a better option (2 amps per channel) - but you would still need proper heatsinking. Also note that these bi-polar drivers drop 1-2 volts to the motor from the battery, so size the battery accordingly (in such a situation, a 14 volt or so battery would be OK for 12 volt motors).
The best solution would be a MOSFET motor driver from a place like Pololu or similar - you'll get better current handling, little to none of the voltage drop as seen with the bi-polar drivers, and mostly or totally eliminate the need for a heatsink (depending on the driver).