the easiest and safest way is to plug in a small dc power supply (say an old phone charger) into each circuit and use these to switch a relay.
you can either have one relay per power supply and connect their "normally open" contacts in parallel or connect the power supplies in parallel with a diode in series with each to isolate them and use this to power a single relay.
in the latter case, if the power supplies can power the fan, there is no need for the relay. (and of course you need a low voltage fan).
the problem with trying to run a 220V fan from between any pair of 110V phases is that you only have two phases and if the two that are on are the same phase, you will get 0V between them.
you would be better off using a 110V to 220V transformer and switching it to a phase that is currently powered. Using DPDT relays and the first option above to power them it is possible to wire them such that 110V from an available phase is switched to your fan (but be careful, accidentally shorting a phase will be exciting in a bad way.