Use an XOR function. (eg. 74LS86).
It works great for me, thanks!
Hang on...now I think about it, it's not that simple. You need some ANDs as well.
If the two inputs are called A and B:
Relay 1 = A AND (A XOR B)
Relay 2 = B AND (A XOR B)
The 74LS08 has four AND gates. Each gate has two inputs and one output for a boolean function. With a 74LS86 and a 74LS08 you can wire up the boolean equations above.
nb. These days you're more likely to find 74HC08 and 74HC86 than 74LS08 and 74LS86, the two letters in the middle (eg. "HC") are just the type of material used to make the chips, their function is the same.
PS: Even this won't protect you against rats chewing the wires or other random cosmic acts. If this is mission critical then maybe you could put a fuse in the power supply which will blow if both devices turn on simultaneously.