Die 4,5 V sollten für den µC reichen, auch wenn es schon die untere Grenze des garantierten Bereichs ist. Wenn man aber Akkus mit etwas weniger Spannung nehmen will, sollte man überlegen vom Mega32 auf den neueren 324 umzusteigen. Da hat man mehr Luft für eine niedrigere Spannung.

der 7805 ist für den Batteriebetrieb eher weniger geeignet da gibt es bessere Regler (z.B. LP2950, LM2931), die weniger Strom brauchen bzw. mit weniger Spannung auskommen.