Intterupts For Arduino
An interrupt can not always stop the code, although that is almost always the case. Certainly having an interrupt based kill switch would be better than a "regular code" polled one, which would still be better than nothing. If possible I would feel safest with a cut-power-to-the-whole-thing style safety switch.

Many functions that have sensitive timing constrains disable interrupts while they are active. It is rare for any of these to take a noticable amount of time, but it is possible that a bug in an interrupt dissabled function or another interrupt function could cause it to block and in that case your stop switch wouldn't work. rare, but possible.

I suppose you could turn on the chip watchdog timer, have a regular timer based interrupt reset the watchdog timer at a certain interval, and have your interrupt safety switch enabled. Then if interrupts ever stopped firing for too long the chip would reset itself. Checkout AVR132: Using the Enhanced Watchdog Timer. I've never used the watchdog myself, but it exists for a reason.

I don't have enough experience with a scheduler system to know if they would be helpful.