Hallo!
Wer sagt denn, dass ein AVR bei 4,5V aufhört zu arbeiten bzw. abstürzt?
Falls man nicht die vollen 16 bzw. 20MHz braucht, kann man da locker bis 2,7V runter gehen. Je nach verwendeter Hardware ist es eigentlich ganz einfach, das System auf 3,3V um zurüsten. Dann würde auch ein (Akku-freundlicher) Step-Down Regler ausreichen (z.B. LM2576, die sind ganz einfach aufzubauen).
Die Motoren würde man in dem Fall direkt an den Akku anschließen. Alternativ dazu könnte man auch über einen kleinen 3,7V LiPo für den Controller und einen anderen (6V Blei?) Akku für die Motoren nachdenken.

Gruß
Basti