Shpaget:
Hmm, would a bistable (latching) relay be a good idea? A button activates it, a circuit is closed and the power to the Arduino starts flowing. Arduino does its thing and when it's done it turns itself off by pulling its own plug.
I've used such a method on a couple of projects using a single coil latching 5vdc relay.
http://img25.imageshack.us/img25/563/08miq7.jpg
Lefty