Except that the two actions (pushing onto the stack and then clearing the interrupt) need to be atomic
Why is that? If the interrupts were already disabled, there is no way the two actions could be separated by an interrupt. If the interrupts are already enabled, what is the difference between an interrupt firing before the push, or an interrupt firing between the push and the cli? I don't see how it could be a problem.
In any case, ATOMIC_BLOCK( ATOMIC_RESTORESTATE ) isn't atomic at that point, either. The compiler implements it by saving the __SREG__ in a general purpose register. In my case, it was r24. Then it executes the cli.
; ... My block of code that can't be interrupted