This problem starts to become interesting... I think I soon have to put together that circuit and test it myself with an oscilloscope.
From point 2 above: That the MOSFETs get destroyed at approximately the limiting Vds (100V), could point to that they don't work well in the avalanche sequence and that one transistor (after the other) ends up carrying the full voltage.
A killer could be that the circuit is too slow to switch the higher current, thus the maximum power, (U*I)ds could be exceeded in the switch-on or -off slope.
1. You could try to switch a pure 80 ohm resistor instead of the coil and see if the result is the same.
2. You could try to reduce the gate resistors. Instead of 10k use 100 ohm. That will speed up the circuit very much.
Normally MOSFETs are very good at withstanding over voltage when a load is connected. That's because of the Avalanche Rating that is also built into IRF540. It means they simply start conducting when an over voltage appears. I have used MOSFETs switching very inductive loads, at high current, without any freewheel diode or snubber. The MOSFET catches those spikes wonderfully. It must only be assured that the max. power is not exceeded (P=clamped over voltage * current).
In fact, in the suggested circuit I don't think that ZD11-16 are necessary if it would work properly.