What you're looking for is a relay. I don't have experience with mains voltage ones, just the 12v DC. When the power goes out it automatically switches an appliance on or off. It's very cheap, but requires proper installation since you're dealing with high voltage/current. You can find these relays at any electric shop and any semi-capable electrician should be able to install it. Make sure to install it inside a plastic electric box so that no one messes with it.
You have 2 kinds of relays, the regular ones which will cost you around 5 bucks and the Solid State ones which will cost you around 50 bucks. In the end the relay you're gonna end up with depends on which one the electrician is familiar with.
Here are some pictures from a Lebanese re-seller (Ketranji)
Regular socket relays:
http://www.ekt2.com/products?cat_id=7cf77f6e-2324-454c-bde1-fc667bf0ad6e
Solid State:
http://www.ekt2.com/products?cat_id=54bad170-0fef-4e6f-9c9a-77189d1f196d
Just make sure to choose something that can handle at least twice the amps of the fridge. Meaning go for 10A or higher.