Are function pointer assignments atomic in Arduino?
Have a look at the code for attachInterrupt() and detachInterrupt() in
/Applications/Arduino.app/Contents/Resources/Java/hardware/arduino/cores/arduino/WInterrupts.c (well, that's where they are on a Mac, anyway. Arduino file structure on other OSes' probably looks similar in the lower levels of the path).

It appears that attachInterrupt() assumes that the interrupt in question is not yet enabled because it writes the function pointer without taking any precautions. Note that detachInterrupts() disables the target interrupt before writing a NULL-pointer to its vector. So I'd at least use a detachInterrupt() / attachInterrupt() pair

I'd want to run any such code in a critical section, myself. It appears your first way (detach, then attach) would work, though I can't be sure it couldn't miss an unfortunately timed interrupt. The datasheet for your MCU might have more to say on that. But neither am I sure at this point, that a global cli()/sei() wouldn't miss it either. The ATMega2560 datasheet, section 6.8, does say "When using the SEI instruction to enable interrupts, the instruction following SEI will be executed before any pending interrupts, as shown in this example", seeming to imply that it can buffer an interrupt while the interrupts are off.