All your problems (heat, current etc) are interrelated.
You could use motors that draw less current but where would be the fun in that? Let's see if we can get this working with what you've already got.
First to avoid damaging your arduino, try connecting the external supply dirctly to your motor driver circuit first then take the connections from there to the arduino, ie power goes to SN754410 circuit first, then to then arduino Vin from there. This will stop the high currents drawn by the motor from flowing through the arduino PCB.
As for reducing the current drawn by the motors, you could try PWM (pulse width modulation) to reduce the "on" time of the motor drivers, which will reduce the average current being drawn. This is easily done using the analogWrite command and setting a value less than 255. The SN754410 can handle up to 2A pulsed non repetetive currents for < 5msec so this may work. The only problem with this method is the motors will run more slowly because the average current is lower, and this may be slower than you might want them to run, maybe not even fast enough to overcome the static friction in the motors themselves -> they might not turn at all!
The SN754410 uses bipolar output transistors and if you look at the data sheet it specifies typical voltage drops of 1.4V and 1.2V for VOH and VOL at 25 deg Celcius when passing 1A. Knowing that Power (P) = Current (I) * Voltage (V), this equates to 1.4W and 1.2W (2.6W total) if you're using the full H-bridge mode for a single motor. The data sheet says that the device is rated to approx 2W continuous at 25 deg C, so no surprise that it is getting hot.
You could use separate driver ICs for each motor, this will reduce the power dissipated in each driver IC as the current will be halved, this in turn will reduce the heat generated in the IC, or try a different motor driver IC with lower "on" resistance. Perhaps a driver using MOSFETs would be better since they can have very low on resistance (R) and P = IIR, if your reduce R you get less power dissipated as heat in the device.
If you still have heat problems, the only solution is heatsinks on the motor drivers... either more copper connected to pins 4, 5, 12, 13 or if this doesn't work, bond the body of the IC to a chunk of metal, a proper finned heatsink is best. Don't forget to use heatsink paste to achieve proper thermal bonding. Maybe even use a fan to force air over the IC and heatsink?
It starts to get technical if you want to calculate the correct size and thermal properties required for a heatsink in your application, but it can be done. It has to do with keeping the temperature rise inside the SN754410 below the maximum junction temperature knowing what power the device is dissipating.... a topic for another day perhaps?
