con un relé normalmente cerrado podrías hacerlo, cuando circule una corriente en su bobina, este abre el circuito, y cuando deja de circular (corte de corriente electrica), el circuito que alimenta al arduino se cierra y empieza a funcionar
Acá te hice unos circuitos que muestran mas o menos como debería de ser tu conección, y como funciona, el interruptor de la izquierda simula un corte de corriente, y el led pasaría a ser tu arduino, fijate que al estar el interruptor cerrado(circula corriente), el arduino (LED) no se enciende, pero cuando el interruptor se abre (corte de corriente), el arduino (LED) se enciende.
yanpi una pregunta depronto vos conoces alguna referencia de una rele de pequeño tamaño cuya bobina funcione a 120 V que sirva para este proyecto dado que lo que conozco en estos voltajes son contactores y es muy grande me imagino para la aplicasion.