Arduino shut down.

I am working on a project that has a very low power constraint. It has to operate on very less current, do I chose to use a bare bone Arduino. And I want it to shut down after 1 minute of inactivity. I found out such resources in ZolaLab website:

But I have another condition too, i.e, it has to start by itself when it is powered on for the first time (in our town, there is power failure frequently) which is not possible using the above circuit.
I decided to use a 470uF capacitor in place of the switch, but it has to be a discharged every time after Arduino boots up.
Can anyone help me by giving other possible solutions.
Thanks in advance

How about just putting the Arduino to Sleep --- then waking it up on an "event" [I'm not sure what the event would be -- your description wasn't that clear].

Have a look at this: Arduino Playground - HomePage

To get really low power you will need to use an Arduino compatible board that’s better suited to battery use.
You do not mention what event is expected to power on the Arduino again so either sleep most of the time or use a device like this to do the work for you.