Welcome to the forums.
I will take a crack of this one (come on lurkers, I know you are out there, speak up!!).
You don't mention it, but I assume you don't any any Opto involved in this requirement?
If so, let me know because it will change things a bit based on what inputs you have etc.
Here is what I came up with as a first pass;
In a nut shell, if any of the 4 inputs have power, the coil to the SPDT relay will have power.
If all 4 inputs drop out, power to that relay will stop and the relay will drop.
Usual disclaimer, I might have missed something in your description and so it may not work like you intended.
Also, since mains voltages are involved, you probably should not build it, I'm not qualified to design mains voltage circuits. (Note the lack of a fuse for starters!).
All that said, how close did we get?
Anyone else got a better way to do this?