You know how the Dracthyr were in stasis for 20,000 years, I kind of wonder if something similar would be done with playable Naga.
For example say after the Naga first came into being, a group of them in horror of what they became, rebelled against Azshara. However instead of killing them, she just froze them in time to serve as an example of defying her. And then her leaving broke the spell or we rescue them as apart of the questing experience.