At the risk of being branded a microcontroller bigot (I'm not,
really!), why not do this solely in the mcu? Debounce is pretty easy
(most bouncing occurs for about 1-2 mS, according to Horowitz/Hill)
in software. Of course if your MCU is busy doing other things, you
may not be able to watch the switch.
Your dual interrupt idea works though you would need an external
inverter. Can you trigger on leading or training edges? You might
be able to get away with bringing the switch into a port and watching
the transitions on it. If the responsiveness needs only to be in the
100s of mS range, you could poll the pin every 50-100 uS and use a
little state machine to determine switch state (i.e. debounced).
External debounce can also be done with a resistor and a cap. H/H
has a discussion of this. Sorry, I'm too lazy to look up the page.
As usual, there are at least 100 ways to skin this cat.
Phil