Ianp idea is pretty good.. However I would rather use an N-Channel power FET ( with a digital level gate) as they have few advantages over P-channel.
- easier to source than P channel
- more choices of RDS on in small power version.
As you did not mentionned the current required by your relay it is difficult to mention a specific type, but definitely the idea of a FET is exellent.
The internal diode avoid the use of an external one generally needed in a bipolar transistor solution.
Voltages of 80 to 100 volts (Drain - Source) are pretty common today (2005) and not expensive. Therefore you get yourself 'safe' when switching off the relay of the coil voltage produced.