Hello Kashyap,
Here are my suggestions:

1.Use an optocoupler to sense mains failure, the popular ones in India are PC817, MCT2E etc.There are many circuits available, a more precise method is to make a zero crossing detector and connect to one of the INTx pins of the microcontroller.

2. Super caps may not power the RTC for long periods, and Nicads, have mechanical problems, the leads get cut, if you dont secure the battery properly, instead the 3V lithium (CR2032) is a much better choice, a very compact holder for this battery is now available in our markets, I am using this in one of my recent commercial products.

3. Philips PCF8583 is my choice, it costs half the price of a DS1307, has 256 bytes of battery backed up RAM and consumes approx 1uA, and is available in SMD packages, you can get it from Elektronika Sales, Chennai.

Regards,
John.