Redesign using latching relays
I've come up with a design using latching relays. It's a lot simpler and more robust than the other design.
The relays are Omron G2R-2-DC12 types which are available from Farnell I think. These are latching types which retain their state, and have two coils, connected independently. (Some latching relays have the coils commoned; they won't work with this design.) You also need the contacts to be DPDT (aka DPCO), at least for K1. The coil currents are somewhat significant; the values of C1~3 and R1~3 depend on them, so compare the coil currents if you want to use a different type.
If you have trouble getting that relay type, you should be able to get them from Digikey or Mouser. (I haven't checked though.)
Here's a circuit description.
The initial state is with K1 in the SET state. The contacts are opposite from the positions shown in the schematic. In this state, the left side of R1 is connected to +12V through the bottom set of contacts on K1. This charges C1 up to 12V in a fairly short time (less than a second for it to reach near-as-dammit to 12V).
This voltage sits on C1 until the pushbutton is pressed, at which time D1, D2 and D3 all pull the bottom ends of the four relay coils to ground. Any relay coil that has a voltage on its top end (the positive side) will activate. In this case, K1's RESET coil and K2's RESET coil will activate. These coils draw significant current (50 mA each, so 100 mA total), which mostly discharges C1 in around 0.1 seconds. This is long enough to flip the relay states though.
K1 flips to the RESET state, and K2 is also forced into the RESET state. With K1 RESET, the +12V supply rail passes through K1's top contact set, onto the line labelled "ON", which is active when the heater is ON. At the same time, K1's bottom contact flips to 0V and R1 helps to discharge C1.
Since K2 is RESET, the +12V voltage on the "ON" line is fed through its top contact set onto the "LOW" rail, which supplies +12V out to the low power heating elements in the seat warmer. It also feeds through R2 into C2, but C2 will not charge up much while the pushbutton is held down, because K2's SET coil is in parallel with it, and it has a resistance of 170 ohms. R2 and this coil resistance form a voltage divider that only allows C2 to charge up to about 2V, which is not enough to have any effect on K2's SET coil.
Once the pushbutton is released, C2 is free to charge up to 12V through R2. When the pushbutton is pressed next, the stored charge in C2 is dumped into K2's SET coil, flipping K2 from LOW to HIGH and powering up the high power elements in the seat warmer. The low power heating elements are now not powered.
In this state, when the pushbutton is released, C3 charges up through R3 to 12V, and when the pushbutton is pressed again, C3's charge is dumped into K1's SET winding, returning K1 to the SET state and turning the heaters OFF (the "ON" line is no longer powered).
You might think that K1 is used backwards; it is SET when the heaters are OFF and RESET when the heaters are ON. That is true. I did it that way because these relays need more current in their SET coils than in their RESET coils (because of how they work internally), so the two coils that are paralleled should be the RESET coils, which draw less current. That's the only reason I did it that way.
D4 suppresses back EMF from all of the coils. I'm not sure whether it's actually needed in this circuit, but better safe than sorry - it's only a two cent diode.
You can see from this description that you have to wait a short time with the pushbutton released before you press it again. Half a second should be long enough. This gives time for whichever capacitor (C1, C2 or C3) to charge fully, through its respective resistor.
The RGB LED is driven directly from the heater supply voltages. The 330 ohm current limiting resistors will give a current of about 30 mA for each colour. The LED is the only component that requires any special handling precautions. I would actually recommend tacking a tiny multi-layer ceramic capacitor across each of the elements that are used. Keep all the leads shorted together as you remove it from the package, bend the green lead and short it to the cathode, then solder a little MLCC (0.1 uF or something like that) from red to cathode, and from blue to cathode. Then you can handle it however you like.
Edit: This circuit draws no current from the automotive supply while the heaters are OFF.