To prompt a menu with a button I would use ext int0 or int1.
Interrupts should only be used when necessary and then only reluctantly and to the least extent possible. There is absolutely nothing about handling button input that requires interrupts, and using interrupts introduces a lot of design issues which will just make it harder to get a working solution.
To display the menu system I suggest you implement a state machine to keep track of which menu is currently displayed. It is easy to read and debounce buttons and detect transitions yourself following the examples that come with the IDE, or you can use the Bounce library to make it even easier. The output either way would be that you know when a button has been pressed and which button it was. You can use that to trigger code within your state machine. Simple state machines like this can be implemented by defining a set of constant values representing the different states, defining a global variable to hold the value representing the current state, and using a switch/case statement to execute the code corresponding to the current state.
Since you want to control multiple things at one you should use a non-blocking approach - Robin2 posted some example code which demonstrates this technique very well: http://forum.arduino.cc/index.php?topic=223286.0
To save the configuration values I suggest you define a struct to hold the current configuration and use the EEPROM write anything code fragment from the playground to write it to EEPROM each time the configuration changes, and read it back from EEPROM at startup.