Un diodo en serie con la batería haría el trabajo de "desconectarla" cuando le aparezca una tensión superior. Basicamente
conectá los 12V directamente a la entrada del 7805 y los 9V a través de un diodo (1N4007 o equiv) de tal manera que el ánodo del diodo esté en el positivo de la batería y el cátodo en la entrada del 7805 (y los 12V). las masas son comunes.
Cuando te aparecen los 12V el diodo que polarizado inverso (-3V) y no conduce (la bateria "desapareció").
La desventaja: cuando está solamente la batería tenés la caída directa del diodo (0,7V), podés usar un diodo schottky (1N5381, creo) que tiene menor caída (0,2V).
Saludos
Marcelo
PD: mejora: también ponele un diodo en serie a los 12V (los cátodos de ambos diodos a la entrada del 7805, un ánodo a los 12v y otro a los 9V) para evitar que la bateria se descargue por algún corto en la entrada de los 12V