ExperimentUno:
Io opterei per una alimentazione da rete e con un alimentatorino di quelli per caricare il telefono collegarlo all'Arduino, magari saltando l' ingresso del regolatore. Eventualmente aggiungere un condensatore da 1 mF.
Volendo passare dal regolatore dell' arduino si potrebbe prendere un alimentatore a 9 Vdc (tipo questo) poi alimenti il relè direttamente dall' Arduino, che lo dovrebbe sopportare incluso il modulo bluetooth che ovviamente vorrai mettere.
Invece del bluetooth sto usando un receiver a 433Mhz con antenna, ho testato la distanza tra trasmitter e receiver e ci siamo.