Grazie Leo,
premetto che sono un informatico e con l'elettricità/elettronica (come si vede) non ho una gran esperienza!
In effetti l'idea del relè forse è la cosa più semplice 
Una batteria USB tipo questa: https://www.sparkfun.com/products/11358
dovrebbe fare il suo lavoro giusto?
Da quanto ho capito, se utilizzo una batteria USB (che fornisce 5.5V) e un alimentatore diciamo a 9V Arduino dovrebbe assorbire dalla batteria solo nel caso venga meno l'alimentatore. Se questo avviene in automatico, immagino che la scheda Arduino non si resetti mentre avviene lo "switch" di alimentazione (il che sarebbe noioso), giusto? In un certo senso non dovrebbe accorgersene nemmeno 