There is a great deal of variability when looking at high speed changes in power draw. It isn't as easy as thinking about what might happen at DC. Some of the issues can be based on the length and size of conducting wires, as well as the configuration of power routing. This applies in both wiring and PCB routing of a power system.
It is possible common to have a power demand pulse quick enough that you have to think of power bus as a transmission line, rather than a lumped circuit element. The inductance of your power supply wire will resist current flow enough to drop the voltage a significant amount at the end of the transmission line. So in this situation, a diode and capacitor may solve the problem by keeping Arduino voltage high until the current can make it down the wire to fill the need.
It is a good idea to isolate the control and high power demand variation circuits. This doesn't have to be as much as a separate power supply, but could mean just not sharing long runs of power supply wiring, before T'ing off to each other.
You don't say it, but your problem may be that you're trying to start the stepper at full speed. If so, there is a maximum speed (which varies somewhat with load) beyond which a stepper will not accelerate, and this speed is normally well below what you can reach with a gradual increase in speed. Google on "stepper motor torque curve".
The problem is that, with a 4-phase stepper such as you are using, if the shaft angle lags more than 2 step angles behind the commanded angle, the torque reverses and the motor sits and vibrates and makes horrible noises. This is not, technically speaking, a stall condition, where the shaft does not move at all.
The torque-speed curve for your motor can be found at http://www.kelinginc.net/KL34H2120-42-8AT.pdf and indicates that the motor can be run at 5000 steps/second, which suggests that your problem is your attempt at fast start.
If, on the other hand, you've already tried a slowly increasing step rate while running, then you probably do need a heftier motor. However, my calculations for a .144 hp motor at 10 rps gives about 2 Nm torque, and the linked torque curve for your stepper is about the same, so I wouldn't expect a problem. Unless, of course, you've modified your mechanical setup somehow.
Best Answer
Note that the amount of force (Newtons) available from a motor depends on how far away from the center of rotation you are, because torque is the product of force and distance. (We measure torque in Newton-meters or pound-feet or somesuch unit.)
A gearbox or pulley will give you close to the exact ratio of torque increase; a pinion with 12 teeth driving a sprocket with 60 teeth will give you about 5:1 torque increase, with the corresponding 1:5 decrease in rotational speed. Same thing for a belt or any other kind of rigid ratio.
Regarding "not skipping steps," you will want to add limit switches no matter what. Even with brushless motors, as suggested in the comments, you need to know how far to move, and unless the BLDC has an absolute encoder attached, you can't guarantee the exact stop position without limit switches.
Stepper motors are reasonably tolerant to light over-volting, or even over-current-ing, because they have very few moving parts, and no brushes to wear out. Also, if you only run them for a short amount of time, there won't be as much heat build-up, and thus you can run them at higher current for a shorter duty cycle. If you can crank up the voltage, and turn the motor driver up to maximum current, that might be enough. Or not -- the L293D is not a high-performance driver.