Powering a stepper motor without a 9v battery
it appears what you need here is a 2 cell lithium battery. Li-po(nominal 7.4) or li-ion(nominal varies, but more than lipo) would probably both work. Worthy of note though, is that adding a lithium battery to a project safely  adds quite a bit of complication. Unlike other battery chemistry, these do not drop to 0V at discharge, but are considered "discharged" when there is still over 3V at the terminals. Discharging the battery farther will cause damage to the battery and most chargers will refuse to recharge it. That being said, as long as this isn't an autonomous project, any method of checking the voltage will work. The vast majority of modern RC cars use 2 cell lipos, so they can be had for resonably cheap. 
http://www.hobbyking.com/hobbyking/store/__6540__ZIPPY_Flightmax_2200mAh_2S1P_20C.html
You also need specialized charging circuitry as well. 

If all of this is too complicated, you should be fine with 6 AA batteries. You can buy whichever rechargeable brand you like. That will give you approximately 4X runtime of your current setup and requires no voltage monitoring. 

With regards to power supplied to the stepper:
Most steppers don't care much about the voltage supplied to the terminals, as the insulation is rated for much higher voltage than you could apply with simple batteries. What they do care about is amperage. More specifically heat If the motor is getting too hot to old onto chances are you are on your way to burning it out. Steppers are 2 phase brushless DC motors, and the permanent magnets inside will become permanently not-magnets if they get too hot. 
Looking at the easydriver website, it appears there is a current limit setting on the driver. Set that somewhere under the maximum rating for that motor and you're good to go regardless of input voltage.
Cheers.