Stepper motor power is defined by both speed and the inertia of the load. Remember that if you are driving a stepper motor at a low speed, you are accelerating the load from a dead stop to the next step, then decelerating the motor to a stop. The motor can go full current accelerating on each step, because non of the angular momentum is retained from the last step. Motor can get hot, but you probably won't hurt the controller. You may "lose your place" by missing steps if you try to run too fast.
If the motor load and speed are in the "sweet spot," the system can be more efficient, but since there is no feedback the load and inertia would have to be matched to the motor characteristics. Manufacturers sometime give speed specs under optimal conditions, so be careful. In general, you would not want to use steppers in applications where you are running everything continuously. They are good for applications where cost needs to be low and efficiency is not required (usually low duty cycle). Your controller probably allows you to make some current settings to help keep the motor from overcurrent condition.
Torque is directly proportional to current, and increasing voltage allows you to run at higher speeds.
In answer to your questions, you can experience heating in the motor if the load varies. A controller will continue to pulse when the motor is stalled, but since none of the power is going into work, it all goes into heat. Run as slow as you can and keep your max current low so that when these conditions occur you won't overheat. Keep your duty cycle low if possible.
When you choose a lower current, you limit the speed because the motor will accelerate more slowly, requiring more time to get to the next step. Microstepping might be a little less efficient, but with smart controllers it is probably not much, and it will definitely "smooth out" vibration when running. Running at a lower current should reduce the power per controller, and the power draw when stalled is about the same as max load, with the caveat that things are getting heated. Get some big heat sinks and turn the motor power off if you don't have to hold torque. Forced convection cooling might be an option to consider.
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.
Best Answer
The NEMA number specifies only the physical size of the motor. Motors with the same size can have different torque / current rating / voltage rating etc.
Generally, motors with the same number of steps which dissipate more power (amp rating multiplied by voltage rating) will have more torque since you're putting more energy into the rotor to make it travel the same angular distance.
All of these parameters should be noted in the motor's datasheet, so when you need a motor with a specific torque, look for its torque rating.