The L293D is NOT a good choice and will NOT run your motors if your battery voltage is too low. 4.5V is definitely too low.
The motor you appear to have requires about 4.5VDC and a maximum of 250mA.
If you want to run 4 motors simultaneously you must allow for a total of about 1A from your battery supply.
The L293D has an output driver stage (each half of the H-bridge) that looks like this:
This type of configuration drops significant voltage from the VCC2. You should attempt to read the datasheet for the L293D and notice that the output high voltage is specified as typically 1.4V less than VCC2 ...AND the output low voltage output is typically 1.2V.
This means that setting VCC2 at 4.5V may result in 4.5 - (1.2 + 1.4) = 1.9V left to drive the motor. The results may be far from spectacular at this voltage.
To ensure that you could drive the motor at 4.5V, you would need a VCC2 of at least 4.5 + (1.2 + 1.4) = 7.1 volts.
You could use 6 * 1.2V AA batteries and achieve motor drive for a short time. You should look at a battery datasheet to understand why the battery life would be short. Here is the dataheet on an Energizer battery, Notice it will not provide good life at 1A, so AA seems like a poor choice.
If you must stay with AA battery size, then you could use a Lithium primary cell such as this Energizer AA Lithium version. This has a higher terminal voltage so you'd only need 5 of them to get you required 7.1V and a much better runtime.
You don't detail how you will drive the motors (PWM or simple Fwd/Rev signals). If you are using PWM then you could increase the VCC2 voltage to say 9V and expect to get reasonable results.
Update: You can increase the voltage across the motor when using PWM since the motor responds to the RMS value of the input power (voltage and current). In the case of the motors you have if 4.5V supply was the recommended maximum you could apply, then a 9V supply (PWM=100%) would result in 6.4V across the motor. In reality however the motor has a range of potential operating voltages that would work, so likely your motor would be fine from perhaps as low as 2V to as high as 6V, so providing you don't go to 100% PWM the RMS rating would not be exceeded.
NOTE: VCC1 is normally at the same voltage as your driving MCU, so if the MCU is 5V then VCC1 would be 5V.