Marshmallows will dissolve ("melt") in your hot cocoa for the same reason that they "melt" in your mouth: both provide heat and moisture. If you could somehow treat the marshmallows so that they didn't dissolve in the cocoa you wouldn't get the desired effect in your mouth either. It comes down to a matter of timing: how can you keep the marshmallows intact until you drink the cocoa?
I can think of three options:
Drink the cocoa more quickly.
Use larger marshmallows.
Add more marshmallows as necessary.
It's not clear from your question exactly what kind of marshmallows you're referring to. I suspect that you're talking about the crunchily dehydrated "micro-mini" marshmallows that come in a packet of hot cocoa mix. Call me a snob, but those things hardly qualify as a "marshmallow" at all; you should perhaps be happy that they dissolve, or else sift them out of the mix and throw them away! If you like them, though, you'll be happy to know that you can buy more: Amazon carries 12 oz. bags of dehydrated micro-mini marshmallows, and adding a spoonful to your cup when you're ready to drink should solve the problem.
If you feel like an upgrading your brew, pick up a bag of mini marshmallows and add a handful of those. Minis should be large enough to last for quite a while, and since they're not dehydrated they'll be somewhat sturdier in the cup. Marshmallows come in a number of sizes... if the minis don't last long enough for you, go with a few standard sized (approximately 1 inch) marshmallows. I've seen jumbo marshmallows in the store lately, but you'll probably need a larger cup if you want to have any room left for the cocoa. Try one of these lovelies.