Stepper Motor vs DC Motor with Relays
NO!

Stepper motors, as I'm sure you know, move in steps: whenever your Arduino tells the motor to take a step, it takes one step: often 1/200th of a rotation. They are designed for very high accuracy at the expense of efficiency.

However, that said, they are good motors, you just have to drive them right and not ask them to do what they can't. 95% of problems people have with steppers come from expecting something unreasonable. 

The secret to steppers is that the voltage rating means (almost) nothing. In order to get a stepper to produce torque, you have to get current flowing through the windings, which are just big coils of wire with lots of inductance. The result is that, if you're stepping quickly, the current doesn't have time to ramp up to it's full draw. 

Graphic example here: I once was driving a medium-sized stepper the same way you were. When it was sitting still, it would draw about 0.7 A/coil. When it was spinning at 5 revs/sec, it would draw about 0.15 A/coil. That's a lot of lost torque.

The solution is to turn up the voltage. With a LOT of voltage, the current will increase MUCH faster, leading to more torque at higher speeds. However, this requires trickery. If you were to just turn up the voltage on your supply, you motor would overheat when it was sitting still. The solution is to have a special drive that can limit the current and turn down the voltage the instant the current hits the rated value.

In fact, this is so much better that some steppers don't list voltage ratings - just current ones.

Some tips for getting them to work:


Don't use the Velleman motor shield. It's just a L298, legendary for bad performance with high internal resistance and no current limiting - a must for good performance (as described above). 
For a solid constant-current driver, take a look at the DRV8825: I've used these with success before, and they're dead easy to wire up.
With a constant-current drive, the higher the voltage, the better. You don't have to worry about too much current with the special driver, and more voltage = current ramps up faster = more torque at higher speed. THe ones that I've linked above can run at up to 45V (I recommend you go with 36V or less, due to voltage spikes), but it's not uncommon for big steppers to run at 80V or more.


Don't forget to ramp your motors up and down! It is a HUGE mistake to just try to start out at the speed you want: your car can't go from 0 to 60 in an instant and neither can your motor. Arduino has a great AccelStepper library that makes this pretty easy.



Brushed DC motors (the 2 wire kind you can control with a relay, NOT the 3 wire brushless motors) turn whenever power is applied across them. They just spin until you cut the power. They have moderate efficiency, good torque, and have lousy inherent positional accuracy. Whereas with a stepper, you could just trust to the stepper's natural positional accuracy, with the brushed DC motor you will need separate sensors to determine the position (like encoders). Brushed gearmotors with encoders (basically servos) are VERY good for speed, efficiency, and torque.

Your system may work with brushed motors, but it will take a redesign.