You definitely have a lot of options available. The Arduino itself will draw about 30-40mA, so well within the 100mA you have available from your step-up converter.
You can hack the device to solder on to a USB cord (it's OK if the data wires are unconnected), but it's easier to just take the output of the step-up device and connect it right to the +5V output pin of the Arduino. This is not an officially approved method of powering the board but lots of people seem to do it with no ill effects.
I wouldn't recommend running the Arduino and motor board off a standard 9V battery. Those have very low energy storage and their voltage drops down by a lot when you draw lots of current from them (when powering motors for example).
--
The Gadget Shield: accelerometer, RGB LED, IR transmit/receive, light sensor, potentiometers, pushbuttons