Consiglio acquisto gruppo relè

si, la prima soluzione.
Perche' usando due alimentatori separati hai meno problemi di eventuali disturbi generati dalle bobine dei rele'. Sopratutto se l'alimentatore che hai da 5V 1000mA non e' di qualita'.
E poi, se vedo bene, quella scheda rele' ha dei fotoaccoppiatori in ingresso, quindi potresti proprio separare le due alimentazioni.

io volevo alimentare arduino con 9V perchè da quanto ho trovato stabilizza la lettura dell'LM35

questa non so' dove l'hai letta, ma e' un po' una bufala.
Arduino, sia che lo alimenti con 7,5V, 9V, 12V etc.... nulla cambia
Tra il jack di ingresso alimentazione e la circuiteria interna c'e' un regolatore di tensione che appunto la stabilizza al valore di circa 5V.

Se vuoi una migliore precisione e stabilita' in lettura del LM35, usa l' analogReference(INTERNAL), che serve ad avere come riferimento per la lettura una tensione stabilizata ( 1,1Volts ) e piu' precisa di quella di alimentazione
Che non e' detto sia di 5V, ma puo' variare anche di un quarto di Volt. Cosa che non da' nessuno problema di funzionamento, ma importante nella formula che usi per leggere il valore che arriva dal LM35 e che viene convertito dal convertitore Analogico-Digitale ( ADC ) dentro all'Atmega328