I was... actually not surprised to see Arya kill the Night King last week.
The reason why is something of a callback, and they did give us a callback to what I'm referencing from Melisandre when she actually says the 'and what do we say to the god of death?' (Not today.) This goes all the way back to the first season.
Look at the call and response and think of word play:
"Who can defy the god of death?"
"No one can."
...and yet, the first thing she is taught is to tell the god of death 'not today'.
Now look at it not like the easy read, "There isn't anyone who can defy the god of death," and instead as though "No One" is a name.
"Who can defy the god of death?"
"No one Bob can."
"A girl must become no one Bob."
This also makes a metric fuckton of sense re: 'yes, there's an aspect of stripping away layers of identity, but not to become someone without any identity at all, but to refine and discard the chaff to become a pure expression of who someone truly is at their core,' which is essentially what she did. At which point, she's told she has become no one Bob.
"A girl must become no one Bob," in order to defy the god of death, because only by going through that process of refinement/focus/etc. can one do so. (ETA: Essentially, only by going through all of that to keep aspects of personal truth/identity rather than being broken down, tempted to easy answers, defeated, etc. is someone able to undertake that kind of challenge.) It turns the statement we've heard the whole time from 'not possible' to 'here is how', and she is even told the call-and-response of 'tell that guy to fuck right off' from season one. Then she's told how, even if this is not immediately obvious.
Melisandre is there at just the right time to give the prompt required: 'what do we say to the god of death' to remind her of the first lesson, knowing she's the one who can do it (shut many blue eyes forever).
The Night King is the closest thing to a 'god of death' essentially in the story, so, uh, I gave that pet theory some extra head scritches the other week. 