I have some Nema 17 steppers and they are big and heavy - overkill for your project I suspect.
The motors that @Zoomkat referenced (which are widely available) have 64:1 gearing so that means 64 x 64 steps (3840) steps per revolution. I don't know whether they would be too slow. You could (perhaps should) add reduction gears to the small motors I suggested.
The ULN2003 boards that drive @oomkat's motors and the motor shield that you mention are much less sophisticated than (say) the Easydriver stepper driver. The Easydriver requires fewer Arduino pins and it can be powered with higher voltages while protecting the motor by limiting the current. It's very hard to know if that sophistication is needed for your project. The Easydriver (and equivalent) boards can only drive 4 or 6 wire stepper motors. Not 5-wire motors. The motors @Zoomkat refereenced are 5-wire motors as far as I know.
Beware that a shield may occupy all or most of the Arduino pins making it difficult to connect stuff that doesn't need to use the shield.
Personally, I think I would start by experimenting with the motors @Zoomkat referenced - even if you buy them elsewhere at double the price they are still relatively expendible as learning tools. If you can find 4-wire versions of them I would go for them in preference.
You can buy plastic and aluminimum angle at most decent DIY stores. Either is a convenient source of material to make fixing brackets.
I can't answer your question about soldering, but a cheap soldering iron is a very useful investment if you are tinkering with Arduinos. The only diffiult thing is being careful not to burn yourself 
...R