Initial power up requirement
A simple way to do this is to put a P-FET in series with the processor's power.  A high value resistor pulls the gate high, which keeps the FET off if nothing else happens.

A pushbutton shorts the gate to ground when pressed, which powers up the micro.  The micro then holds the gate low thru a transistor.  The micro should be able to power up and actively hold the gate low within a few ms or at least a few 10s of ms.  That is still a "short" time to press the button from the user's perspective.  A cap on the gate line can keep it low for a while after being shorted to ground.

When the processor wants to power itself down, it simply turns off the transistor that was holding the gate low.

The reason not to have the micro control the gate line directly is that when off, the protection diode in the micro will pull the gate line low.  By driving a transistor to keep the gate line low instead, you get around this problem.