How can I reduce the speed of motors with given battery voltage?
Reducing the battery voltage by going to a lower voltage would go a long way to alleviate that. Is there anything on your robot that actually needs 12V? Or even 9V? Your motor shield CAN run at 12V but it can also run as low as 5V.

As for your motor shield, look up PWM. Basically quickly pulse power to your motor and it will allow it to run slower.