A number of questions regarding map creation.

And how realistic is the idea of a story-driven multiplayer map in general?

It's quite realistic; they just don't make them very often, but you can still find them sometimes.
TalkBoxForPlayers
This function exists in patch 3.1; it has many features, not just displaying a message to a specific player. If the message is small, I think ShowFlyingSign(messageName, objectName, targetPlayerID = -1, time = 1.0) is the ideal option because it doesn't require any action from the player and is very convenient from a gameplay perspective.

I'm planning for four players, and if it's feasible, each player will have their own storyline. The game will be three against one.

I don't think that's a very good idea. For multiplayer, it's better if the players are more or less equal. In Heroes 3, since you mentioned playing it, there's "The Perfect New World," a good example of a multiplayer map where different players have different strategies and quests (although the quests are limited to prophet's huts, but still). And three against one will always be unbalanced, even if the fourth player is clearly stronger than the other three.