Simply put, it's not at all possible.
We'll take it one at a time:
Snakes for Hair
Snakes are animals. They must be born, grow, feed, etc. I can't imagine anything other than a grotesque experiment in surgery which might result in them being attached to someone or something's head.
Having them "naturally" grow out of something's head is ridiculous. Keep in mind, we're not talking about a symbiotic relationship, although I supposed you could wave your wand and have it explained as such.
Those snakes which opt to meld with the Medusa would have to betray their very nature, however - hunting, reproducing, etc.
Turning Things to Stone
Hahahahahaha ... oh, wait. That was a serious question?
You can't do that. No one and nothing can do that.
If your requirement is "maybe not stone, but a death could count; grey skin, lifeless. an afraid culture might count it as stone" then maybe not the Medusa's sight, but venom could have that sort of effect.
A venom that she "spits" at her victim, perhaps? In their eyes or something? This is really stretching it at this point.
Evolution
I'm being a bit mean and short above, so allow me to explain myself.
You're asking for a creature to naturally evolve these features. Evolution is the non-chance retention of chance mutations.
What this means is that for a species, which, for example, is small, vulnerable, and easy to see by predators during the day, those individuals which have better night vision will have better survival chances (as they will forage for food at night). Eventually the species will either a) Evolve to be nocturnal, with excellent night vision or b) become extinct.
For Medusa to naturally "evolve", a survival imperative must arise to coax those traits into existence. And there is no conceivable circumstance under which a creature's survival would depend on growing another creature for hair.
The other thing to keep in mind is that nature, while wondrously complex, likes simple solutions. Having articulated creatures with eyes, fangs, operating tongues and jaws, etc. for hair, while frightening, is also frighteningly complex. The more complex a creature is, the less likely it is to survive, and thus get a chance at evolution.
From a purely "survival of the fittest" perspective, please envision how those snakes would help Medusa survive.
*They-They would add a high energy requirement to "her" daily caloric intake. *Any-Any enemy would have to get very close to get in range of them *They-They would make noise, possibly even giving her away when she's trying to be stealthy, etc.
What single advantage would they offer, other than being scary? (Which Medusa already is)