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.