We'd want an N-channel FET? Because it's on when held high and in the on state I'm not too concerned about the circuits power consumption
AFAIK, this doesn't necessarily matter. Hi rail, low rail, doesn't matter where the gate of the FET is sitting.
For switching a voltage greater than Vdd of the control circuit, things slightly more messy, though. There are some minor pros and cons to switching hi or lo side on the final switch, regarding drive and pcb layout. But because this is a simple manual toggle, not high frequency, and you generally can't stick a magnet on a plane while it's flying, you shouldn't need anything fancy to drive the FET.
I would suggest two stages, anyhow. A PFET for the final switch and an NFET or NPN tranny for the drive, because this conveniently solves the issue of where the rail to be switched is greater in voltage than the control circuitry Vdd while keeping a single ground plane. A simple pullup on the PFET gate would be used to turn it off, drawing no current while off. When switched on, that bit of current would be tacked on to your energy bill.
As for the micro, well... hmm. Even though this is maybe 30 lines of assembly code, it's quite a long journey by spoon feeding. This is lots of RTFM for the specific micro and probably some trial and error, even for someone with experience, and most definitely a good chuck of time optimizing with test equipment. That's after sourcing the parts and reading those datasheets.
PICAXE or ARDUINO probably can't pull off the "full monty" with the pulsing/reading of the hall effect while asleep. PICAXE for sure, no. ARDUINO might be able to do a simple external wakeup, if you're ok with leaving the hall effect sensor on all the time. You mentioned quite a low draw on this part.
For spoon feeding
1. Use a micro, at all... PICAXE or ARDUINO perhaps.
2. Use a bare micro, figuring out use the compiler/IDE, learning how to configure all the peripherals and whatnot. This is 90% of the uphill battle.
3. Play with the WDT and/or for simpler version just sleep and I/O wakeup.
Or hire someone like me to make this for you.
edit: Actually, if you're in it for the learning process, for the long haul, and if you happen to be interested in PIC micros, I can recommend you go to Microchip website and download their "low pin count tutorial" and play with this starter example code and work through the lessons. You can view the schematic for the dev board and make your own pcb or just breadboard it. Or you can buy that, too.
In addition to the free stuff you can find on the web, I can also recommend Googlium PIC tutorials if you are interested in using any PIC assembly. I have purchased more than a few of them, and they are well written and easy to follow. I learned a few very useful tricks about using the MPLAB IDE through these tutorials. The writer is very experienced. If I had known what I know now, I would have probably started here and saved a lot of headaches I ran into down the road by using less practical fee tutorials and even physical ($$) books (I think Mike Predco probably forgot more than I know, but unfortunately, he forgot a lot of important things for a beginner). By the time I found these, I had already learned most of the content the PAINFUL way. These Googlium tutorials are hands down the best, most practical, most comprehensive I have seen for learning bare PIC assembly. You can probably find a free torrent somewhere, but don't do that. These tutorials are a bargain, already, and the writer obviously spent years thinking them through and laying them out.