If interrupt occurs without pressing the button, it is wired incorrectly. You probably left the pin floating. You'll need an external pull up/down resistor or enable the internal pull up (if switch is connected to ground).
Debouncing is only to avoid having one press registering multiple times. A trick that I find very useful to avoid messy debouncing, is to not use interrupts, but rather poll switch every 50ms or so.