**My clipboard in broken. I can post some of the links. You'll have to find them. Sorry

**
The stepper you pointed out has 4 pins. ATtiny's have 8 pins, including power. So 6 pins left. 2 for stepper motor data (other 2 are power.), 2 for rotary encoder (plus 2 for power). That should work.
If you decide to use the ATtiny:
You probably don't need that $150 controller. Check out this:
arduino.cc/en/Tutorial/MotorKnob (tutorial)
and you'll need an H-bridge from sparkfun. (COM-0315)
-OR-
Get the EasyDriver from sparkfun (ROB-10267)
If you look under the "Documents" section for a Portuguese tutorial... you'll have to translate it.
IMPORTANT: Stepper is rated for
12V you will need a 12V power supply for it, NOT ARDUINO POWER PINS!
Good Luck!