Emperors and kings should surround themselves with guards and not grant audiences to powerful strangers with ambiguous motives; prophesied heroes and legendary mages should be able to defend themselves against all but the highest-level player characters, while their locations and defenses shouldn't remain fixed or knowable; vulnerable unknowns who have a significant role to play in the storyline should perhaps not be present at all, until their roles require them to be. Storylines themselves could do more to prevent plot devices relying on conversations with inherently vulnerable NPCs, and -- though this is getting off-topic -- to prevent the fate of the world relying on a few individuals' survival.
Of course, a large part of the issue is solely a game mechanic (developers can't be expected to account for every major NPC dying when writing/coding alternative quest paths), in which case, yeah, option 3 - I'd much rather a simple message inform me that I've severed the quest path, than have certain NPCs be, as far as the new player knows, arbitrarily invincible.