If a N-Channel MOSfet fits the task then I'd prefer it over a relay.
Relays are mostly useful for switching AC, or when you need the floating contacts, or high voltage isolation barrier.
A 12V 8A solenoid is quite a beast and it can also destroy relay contacts over time, so adding a freewheel diode, and maybe also a snubber is advisable.
For a MOSfet, almost any that can handle the voltage and amps will do.
Some of them have an avalanche rating, and if this avalanche rating is (significantly) higher then the energy in your solenoid, you can even do without the freewheel diode (though I still recommend putting it in).
Most MOSfets are not compatible with 3V3 Gate voltages, but you already mentioned that Ugs of your STP36NF06L is 2V5 so you probably are already aware of that.
But watch out for the power dissipation of the FET. Rds increases at low Ugs. You can already see it increasing to 50mOhm @ Ugs = 5V.
P = I^2 * R => 64*.05 = 3.2W and this is already too much to use it without heatsink, and with 3V3 it would be even worse. Too small a Gate voltage dramatically increases the power dissipation in a MOSfet, and the heat can easily kill it. Even if a 3V3 compatible MOSfet "should work", I'd still put in a better gate driver which preferably can deliver more then 8V to the Gate, and this mostly makes the use of a "logic compatible" MOSfet superfluous.
Do you have a higher voltage available nearby?
If not, you can use a PWM output with a DC of 50% and a voltage tripler from some diodes and resistors.
Hmmm,
Maybe a good old fashioned relay ain't so bad after all...