Stepper motor is just fine for this project. Stpeer motors produce their torque at low speeds and require less of a gear train to perform well at low speed.
Post the part numbers and any other info on your stepper motor and driver so we can give you some better advice as to how to connect things up. If you ran the stepper in unipolar mode you could make a somple driver from 4 MOSFETS and use 4 outputs from your Arduino to control the outputs in proper sequence. I have done this in developing a stepper controller for my own use - Here's the url - http://arduino.cc/forum/index.php/topic,84809.0.html - It is for a freestanding stepper driver, but it started out life as fully Arduino Based.