Vielleicht gehts auch mit einer Charge-Pump, wobei ich dir hier kein Bauteilempfehlen kann.
Oder du lässt den Mikrocontroller mit der Batteriespannung laufen und erzeugst die 5V für das Relais extra.
Bernhard