You also need to consider the current needed by your motors (they are DC brushed indeed) and the power/energy you will lose in your driver.
If you use a 3.7V power supply like provided, and the L293D "eats" 1.2V out of it, you lose nearly one third of your energy. See https://electronics.stackexchange.com/questions/108686/what-h-bridge-drivers-are-preferred-for-applications-controlling-a-low-voltage-m for an very interesting review of drivers.
If I can believe that, it looks like DRV883x is the only reasonable choice. It even allows you to use one cell (3.7V) for the logic and 2 cells (7.4V) or more for the motors. But don't do that with the motors you've got, you'd probably burn them.
Unfortunately the other ST or Allegro devices also covered in the article all need more voltage to work.
Regarding the Arduino, a UNO can't be recommended, too heavy, 5V only, power hungry etc. It won't fly. I'd recommend you use a pro mini 3V3 with some LDO power supply such as the TPS73633. Be careful that most LDO regulators (like 1117) have a too high dropout voltage to be used with a 3.7V input, more than 1V.
I'm not affiliated with TI at all, it just happens that when looking for "the right chip for the right job", I keep having to eliminate the others because of data sheet numbers.
On the SW part however, it becomes difficult to find SW for the 328P. Most addicts have moved to 32-bit CPUs. But that's another debate.