Instead of putting the battery terminals on the common of the relay, put the solenoid terminals on the common pins, and use a DPDT relay. Wire the N.O. pins with power and ground and wire the N.C. terminals opposite of the N.O. ones. With a DPDT relay you only need one control pin also.