No, the body diode cannot be used as a free-wheel diode for the reasons you said. The way to protect the switch and still have decent solenoid performance is to put a Zener diode in series with a regular diode in parallel with the solenoid. The regular diode points up toward Vdd and the Zener diode points down toward the switch. Pick a Zener voltage value that is as high as possible without exceeding the voltage rating of the switch, minus Vdd. The higher Zener voltage you use the fast the solenoid will change. But the higher Zener voltage you use, the greater will be the stress on the switch. So use a switch with as high a voltage rating as you can get. That's how to get the best performance from your solenoid without blowing out MOSFETs.
You are right that putting a resistor in series with the solenoid will speed up the switching, but it will also reduce solenoid current. It is a bad deal, usually, to use a resistor to do that.