Raising the voltage probably won't help you, since you're still limited by the output current of the AA's.
Unless he's at the maximum current of the AA's, that's not true.
Raising the voltage will help.
And yes ofcourse, how could I forget to mention the most obvious

, small wheels and high gear ratios.
The higher the gear ratio: more torque, less speed.