Firstly test one controller + motor at a time with the power supply, with Arduino powered from USB at first - fewer things to go wrong.
Adding 2k2 resistors in line in the logic signals from Arduino to L293D's will afford some protection to the Arduino and is a good idea when
first assembling things.
You can use a 9V or 10V regulator chip to drop the 12V down a bit before the Arduino power-jack - this affords some protection from drop-outs on the 12V power if the motors are pushing it hard.
What motors BTW? Have you ensured everything can take the maximum current drawn from all the motors?
I made my mind-now I take the logic power from usb. I also used decoupling.
The current L293D chips are designed for is 600ma. I provide 12V at 24ohms-500ma. So I should be safe.
I have the L293Ds in sockets for easy replacement-is this a good idea? I mean, will the heat sink be effecient when it consist just of blob of metal on ground pins of the socket? The chips have heat protection, but still... Thanks for your reply, I really appreciate it.
(By the way-I have tested my setup with one motor so far. And it seems to run fine, I am just a bit concerned about the heat dissipation.)