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.
(source: electronics-tutorials.ws)
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: -