Use a D type flip flop with Q bar wired to the D input. Each time the clock pin is activated by a button press it flips the output Q pin. This, via a transistor can drive a relay. You also need to have some contact denounce circuitry to prevent relay chatter. This is a one switch solution.
Above is the basic circuit and input frequency (CLK) is your debounced switch opening and closing. So, you press the switch once to bring the logic level to 1 and the output on Q latches and stays latched even when you deactivate the input switch on CLK. Next time you press your input switch the output toggles state.
Here's a different way of doing it with two inverters: -
The circuit also has debounce circuitry (220k and 47nF) and an output transistor drive to an LED. The LED and series resistor can be replaced by a low power relay coil fed from 12 volts.
If you want to implement the D type circuit, here's a contact debounce circuit that can be used with it. This uses a changeover switch as the input device: -
You can even get away from a relay and use a MOSFET in this type of circuit: -