Actually, only the very outside of a meteorite is heated -- small parts melt and get blown away (called ablation), but the interior stays quite cool. The same principle worked with the Apollo spacecraft, returning from the Moon.
Such rocks don't come with return addresses. Isn't it really a WAG that it came from Mars originally?
It's a complicated story, but basically, Mars meteorites have chemistry and ages consistent with coming from Mars, but not the asteroids. What really nailed it down was the discovery in these rocks of minute bits of argon gas whose isotopic composition identically matches the atmosphere of Mars, as determined by the Viking 1 spacecraft 25 years ago.