Yes it is possible.You don't have to have a rooted device just use a broadcast.
In manifest:
<receiver android:name="com.example.broadcastreceiver.YourClass">
<intent-filter>
<action android:name="android.intent.action.ACTION_SHUTDOWN" />
</intent-filter>
</receiver>
YourClass:
public class YourClass extends BroadcastReceiver {
@Override
public void onReceive(Context c, Intent i) {
if(i.getAction().equals("android.intent.action.ACTION_SHUTDOWN")){
//Fire your code here
}
}};
}
If it sounds impossible,Find another way to do the same thing ;)