Hi

I think the adafruit shield is only good for up to 600ma per coil, but what you can do in this case is to stack 2 L293D chips on top of each other, and add a heatsink. Another option is to replace with a each L293D with a SN754410 (but I think this is only good for 1 amp, but can be stacked too). e.g. http://letsmakerobots.com/node/10509

A 12v2a supply may be enough depending on the voltage of the motors... If they are 5 volts each, then it will be fine, but you will probably need a DC-DC step-down converter. Wattage = Volts * Amps so reduce voltage, get more ampage (bearing in mind some wastage though). I used something like this:
http://www.ebay.com/itm/1pcs-DC-DC-Buck-Converter-Step-Down-Module-LM2596-Power-Supply-Output-1-23V-30V-/370751565112?pt=LH_DefaultDomain_0&hash=item565283ed38

That said, I used an ex-laptop power suply that I got for free that is capable of 19.5v3.5a, and 2 of these converters: one set for 7.2v for the motors, and one set for 5v for the Arduino. If you don't already have a power supply, these are good and cheap (or free)