LED Hula Hoop that Interrupts Patterns with Button Clicks

Hey everyone, a friend and I are designing an LED hula hoop that will contain a range of patterns. We want to add a button that allows incrementing through the patterns. The only issue is that upon button click, we want the current pattern (function) to immediately stop and jump to the next pattern. My first idea on this was to attach an external interrupt command to the button that overrides the current pattern and reads through code that increments the button. Since delay() and millis() timing does not work in external interrupts, this caused debounce issues which I cannot get rid of. If anyone could give some guidance I would greatly appreciate it. Maybe there is a way to make external interrupts work without debounce, or there is a better code altogether to accomplish this?