ndrplz:
Grazie Leo,
premetto che sono un informatico e con l'elettricità/elettronica (come si vede) non ho una gran esperienza!
Siamo in due 
In effetti l'idea del relè forse è la cosa più semplice
Una batteria USB tipo questa: USB Battery Pack - 1000 mAh - PRT-11358 - SparkFun Electronics
dovrebbe fare il suo lavoro giusto?
Secondo me sì.
Se non ho capito male, ti serve giusto per poterti spedire un messaggio, no?
Per quel compito è sufficiente. Al max impiegherà un 1 minuto, 1000 mAh per 1 minuto sono più che sufficienti.
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
Esatto, non si resetta.
L'unica cosa con cui devi fare i conti è l'autoscarica della batteria.