Why dont you use an optocoupler ? For example use a TLP521-1 and connect anode to arduino cathode to gnd. Then connect the emitter to the 12 V collector to the + lead of solenoid. And connect - lead of the solenoid to gnd. And its done. Why use relay while you have much faster ways.