More power from a sparkfun magician chassis.

Hi, I'm new to this but having a lot of fun.
So far I've got a magician chassis with an arduino (in fact a Yourduino, thanks Terry) and a L298n that runs around avoiding obstacles, can be IR controlled and has bluetooth ready to go.

My problem, which seems to be widely shared, is that the motors that come with this extremely popular entry level kit are very underpowered.
Here are the specs for the motors

Suggested Voltage:4.5V DC (work well from 3-6V)
No load Speed:90±10rpm
No Load Current:190mA(max.250mA)
Torque:800gf.cm min
Stall current approx 1A

but essentially it all comes down to the fact that with 6AA batteries powering the arduino board and the motor driver board powered from that, the robot won't run on a carpet
You can see how this is making a mockery of all my other efforts. Just search for magician robot and carpet to see how disappointed a lot of other people are.

A problem this widespread must have been solved many times. What's the easiest, quickest, cheapest way of taking my robot to the next level, i.e. rooms with carpets?

I'm thinking of three options.

  1. New motors that I can get cheap from China and fit in to the yellow plastic things that contain my current gears and motors.

  2. Li Poly batteries. These seem to be a great solution to the immediate problem but a real hassle to maintain. Charging sounds risky, voltage levels need to be monitored, you can burn down the house.

  3. A pack of RC car NiMh batteries powering the Motor driver board directly. This would be the easiest. Will the supplied motors come to life and tear around the carpet if they have a lot of current to draw on?

I'm certain someone has figured a simple fix for this. I'd love to hear about it.

More powerful motors are needed - however are there any that are a direct slot-in
replacement? And the right pinion for the gear trains? Or do you have to replace
the whole drivetrain?

The L298 loses you about 2.5 to 3V from your motor supply so that's not helping.
Also an L298 won't be able to handle larger currents that a more powerful motor will
take (unless you go the route of 12 or 24V motors and keep the current low).

That is so helpful. Thank you very much.