Is it currently possible to shut down an actual rocket (not test reactor with external cooling) while in space and then restart it, without melting significant parts of the engine? If so, how?
It was certainly intended that NTRs under development were restartable, but more importantly a clean shutdown of the engine is clearly desirable so you get good control over your engine burns.
Keeping the reactor cool after shutdown isn't too difficult... you can just keep venting propellant through it, after all. I'm having trouble finding any reference to the shutdown/post-shutdown process for anyone's NTRs right now, but Project Rho has a translation of some stuff from Glushko about the Soviet NTR program with the relevant quote:
Research into start cycle and throttling was performed, along with the terminal stage and shutdown cycle using the remnant heat of a subcritical reactor; reverse systems were developed to minimize post-shutdown thrust.
Details of what the reverse systems were is missing from that translated excerpt, alas. You can read the rest for yourself on this page under the RD-600 section, which lacks a direct hyperlink.
There is an alternative shutdown strategy to just letting the whole thing cool down to ambient and vent a load of your reaction mass out as coolant: the bimodal NTR. This involves strapping on a radiator, turbine and generator with a closed coolant circuit. When the main propellant flow is shut off, the reactor is powered right down but not actually shut off. The closed coolant circuit is run to cool the reactor and drive a generator to provide electricity to the spacecraft between main engine burns, which facilitates handy things like simplified spun gravity (cos you don't have to keep your solar cells pointed the right way) or even a secondary electric propulsion system for a high-Isp cruise, assuming a suitably lightweight engine could be made.
Below is a diagram of a tri-modal variant that included a liquid oxygen afterburner (originally found in the LANTR design) for even more thrust at the expense of Isp. I don't know why that was deemed necessary, but I'm sure the reasoning is found somewhere in the various LANTR and trimodal rocket papers out there.
Low quality diagram taken from Conventional and Bimodal Nuclear Thermal Rocket (NTR) Artificial Gravity Mars Transfer Vehicle Concepts