The best way to melt snow is to put it in a bottle inside your jacket under your mid layers while you're on the move and let your body heat melt it. Do not place it against the skin, leave a layer or two between you and the bottle. It's advisable to always leave your bottle in your jacket in subzero temperatures, it can freeze if left in your bag.
Melting snow by body heat is not a fast process, so some foresight is required on your part, if your bottle is getting empty, and you don't know when you're going to find running water next, then put some snow in your bottle to replace what you're drinking. Dropping snow in liquid water will help melt it faster than trying to melt a bottle of dry snow.
Putting snow in your mouth is fine as long as you're warm, I do it all the time, but you are right that putting snow in your mouth will cool you down, so don't do it if you're already cold.
If you are borderline hypothermic, then it would be unwise to try and expend additional body heat in order to melt snow, you need to get up, get moving, and get warm before you can even try it. This will be more difficult when you are dehydrated, as hydration has a huge role in hypothermia.
One other option for melting snow is using solar radiation. Again, it's not a quick process, and you can only do it on a bright sunny day when the temperature is right. This is exactly how the survivors of the 1972 Andes flight disaster got water while they were stranded at the top of the snowy Andes mountains. They used reflective pieces of wreckage from the plane to catch the suns rays, and put small amounts of ice and snow on them then collected the drips in bottles to drink. They also ate each other... but that's another story.