You can limit the output by robbing current from the bases of the output transistors. Very simple protection for both over voltage and over current can be added this way. This will not protect against a shorted transistor, as that will conduct no matter what the base current. In that case, you need a crowbar and/or a series shut off.
The idea of using a relay is fine. Any relay coil will engage faster than it can release. So the protection relay should be normally off and be turned on by the fault condition. I would use two relays, one with normally closed contacts in series with the output. It will disconnect the output from the regulator when a fault happens. The other relay is across the output (a shunt) and uses normally open contacts. This will crowbar the output for additional protection if the first relay does not engage (or the contacts weld shut, or an arc is sustained across the contacts, etc.).