It’s a missed trigger, with no default action (if you can’t, not if you don’t) and an effect on the the visual representation of the game. So the trigger goes on the stack. Deceiver Exarch would be allowed to be played because players can respond to the trigger once it on the stack.

So what we have here is certainly a missed trigger infraction. Even better, this missed trigger does not have a default action. It looks like the type of thing that would be a default action, but unfortunately is not.

We definitely want to award a Failure to Maintain Game State penalty here. It does not seem like Nigel gained advantage here, but what if he has Mind Control, or something along those lines? It is very easy to overlook advantage and Failure to Maintain Game State should be assigned accordingly.

There is a caveat that allows us to rewind actions, but it would not apply here. Attackers have been declared and a trigger has resolved, we are not partway through an action. The missed trigger infraction does not let us involve objects that are new to the zone in which the ability triggered. While we can flash in Deceiver Exarch it can not be sacrificed.

The Exarch might have been drawn this turn! This highlights the danger in rewinding a missed trigger, something we never want to do. If the Exarch has been drawn this turn then we want to try and minimize the damage from the extra draw. While this might seem unfair to the player with the Grave Titan remember that had they remembered their trigger they could have flashed in the Exarch if they had it.

Summary:
What we have here is a missed trigger that gets placed on the stack.
Remember that triggers do not have a visual representation. Eldrazi Monument triggered at the approriate time, both players just forgot to put that trigger on the stack. When we look at the missed trigger from this perspective I think it makes less sense to be able to sacrifice a Deceiver Exarch, or for that matter any new creature. At the time the trigger occurred the only creature on the battlefield was Grave Titan, and as such it is the only creature able to be sacrificed.

In order to make the point a little more clear, if Abella has a means to sacrifice the Grave Titan (Ashnod’s Altar, Momentous Fall, etc) then she could respond to the Eldrazi Monument trigger currently on the stack. When the trigger resolves she can now sacrifice no creatures that were on the battlefield during the time the trigger happened and must now sacrifice the monument! Remember that we are always looking at what the game state (and the battlefield in particular) looked like when the trigger happened, in this case at the beginning of the upkeep.