I think that Jon Snow will be back. Mostly based on the books (the show doesn't really provide anything for us to chew on).
Warning: even if most of what follows is only fan theories, some of it should still be considered as spoilers.
He may have a way to survive
In the books, Jon Snow is a skinchanger/warg. It seems to be a trait shared among all the Stark children, except Sansa (unlike the show where Bran seems to be the only one). Skinchangers have the ability to perform the Second Life: the act of transfering your mind into an animal (possibly another human) at the end of your life. The most explicit example is shown by Varamyr in the prologue of A Dance with Dragons, but it seems that it's also the case for Orell (Varamyr said that he could still feel Orell's hate inside his eagle).
Jon is conscious of being a skinchanger after his time with the Wildings, but isn't particularly fond of the idea (skinchangers are considered as freaks south of the Wall and have been hunted for millenia: Haggon - "The World beyond the Wall is not for our kind. The free folk fear skinchangers, but they honor us as well. South of the Wall, the kneelers hunt us down and butcher us like pigs.").
Melisandre has a vision about Jon Snow:
The flames crackled softly, and in their crackling she heard the whispered name Jon Snow. His long face floated before her, limned in tongues of red and orange, appearing and disappearing again, a shadow half-seen behind a fluttering curtain. Now he was a man, now a wolf, now a man again.
A Dance with Dragons - chapter 31 (Melisandre I)
Given that the last word Jon whispered just before his death is "Ghost", I think he warged into his direwolf and will stay there for a while. How he will become a man again, I don't know, but my bet would indeed be on Melisandre using the Kiss of Life of the Red Priests of R'hllor (as you said, in the show, we have only Beric Dondarrion as example, in the books there is also Lady Stoneheart).
As the show has not yet included skinchanging in Jon's abilities, I suspect they will keep it that way and simply have him ressurected after some time off.
He may still has a role to play in the story
This is the spoilerish part:
We have been given several clues that he is probably the son of Rhaegar Targaryen and Lyanna Stark (famously known as the "R+L=J" theory, I will not extend on the arguments for this one here, but you can find more informations on the current reference guide on the asoiaf.westeros.org forum).
Also, Jon could be Azor Ahai; in the past, Rhaegar seems to have somehow discovered that the prophesied Prince That Was Promised (who seems to be another name for Azor Ahai) would be of his bloodline. He first assumed that it was himself, and later that it was his son Aegon, but now both are reported to be dead and we don't know if Young Griff is truly Aegon (he claims to have been swapped with another baby before the tragedy). Jon could well be Rhaegar's last living son. In both cases, he's a major candidate for the prophecy known as the song of ice and fire, which would coincidentally fit nicely to a character mixing Stark and Targaryen bloods.
Also, we have a few textual hints:
I pray for a glimpse of Azor Ahai, and R'hllor shows me only Snow.
A Dance with Dragons - chapter 31 (Melisandre I)
And it's not the first time apparently. R'hllor seems to be quite fond of Jon (Melisandre thought about her vision: "Skulls. A thousand skulls, and the bastard boy again. Jon Snow." and later when asked directly by Jon: "I am seeing skulls. And you. I see your face every time I look into the flames.").
Also, Jon has a strange dream shortly before his death:
Jon was armored in black ice, but his blade burned red in his fist. As the dead men reached the top of the Wall he sent them down to die again.
A Dance with Dragons - chapter 58 (Jon XII)
Which recalls the description of Lightbringer, the legendary sword of Azor Ahai:
Lightbringer is thought to be a sword made of living fire.
Of course, we will not know for sure until the season 6 of the show or the 6th book The Winds of Winter. And there is still the possibility that both works will diverge, but if Jon indeed survives only in the books, that would be a major change (the biggest one yet).
About your other question:
Is This Why They Never Brought Back Lady Stoneheart?
You could be right about the idea that the showrunners kept her out to maximize the surprise. But it could also be because she would require a non-negligible amount of screentime to be (re)introduced while being a relatively unimportant character (in the books, she is only mentioned a few times for causing some troubles with the Brotherhood Without Banners and appears once in the context of Brienne's quest for the Stark girls).