How are rocket engine nozzles able to survive very high temperatures without melting?
There is actually quite a lot of information on the subject in the Braeunig web site Basics of Space Flight. To give the salient points:

Liquid-fueled rocket engines

Both the nozzle and the combustion chamber itself need to be cooled. Although most of the thermal energy produced is ejected with the exhaust, some of it will indeed push hardware temperatures up if not checked. Techniques include:


Regenerative cooling, where the propergols (both propergols, or just the fuel) are pumped through a jacket around the nozzle before going into the combustion chamber. This cools down the nozzle, and heats up the propergols that may be cryogenic in nature. This is what was used in the Saturn Vs' Rocketdyne F-1 engines, and the Space Shuttle main engines.
Dump cooling, similar to the above but the fuel used to cool the nozzle is dumped overboard instead of being fed into the combustion chamber and being used as, well, fuel.
Film and transpirative cooling, where a thin film of coolant or fuel is created near the chamber wall.
Ablative cooling, where part of the combustion chamber or nozzle wall is sacrificed. As the material is melted or otherwise burned away, it absorbs some of the thermal energy, thus saving whatever is behind it.
Radiation cooling, where nozzle design is such that heat has time to be evacuated through the part's exterior wall. This is used mainly in small engines, not main.


Solid-fueled rocket engines

No information available. Nothing. Zilch. Nada. 

It would seem that the nozzle and combustion chamber materials just need to be strong enough to withstand the heat from the burning gasses. It is perhaps worthwhile to note that solid rocket engines are designed to burn just one single time, and for a relatively short period of time (even the Space Shuttle boosters were extensively overhauled before being put back into service, with any necessary parts changed). Rocket engines need to withstand working conditions for just minutes, instead of the thousands of hours an A/C jet engine turbine would be expected to work without failure.

It would also be reasonable to assume -though this is strictly something I am making up on the go, with much hand waving- that of the techniques described above for liquid-fueled rocket engines, at least two could be easily adapted to solid engines:


Film cooling, with an extra tank of cooling liquid on board.
Ablative cooling, with some refractive material used to coat the inner surface of the nozzle.