Hola,
Yo buscaria algun dispositvo que te de una señal cuando la alimentacion caiga.... Existen unos circuitos llamados supervisor de reset que te pueden servir pej el max701. Nomralmente estos circuitos resetean el micro cuando la alimentacion cae por debajo de una tension pero los puedes usar como supervisor de tension.... este circuito deberia activar algun tipo de biestable tipo rele que conmute la alimentacion de red por la de las baterias.... es lo mas sencillo que se me ocurre y no necesita programacion.
Un saludo,