In reply to valjean: Never happened to me, but I suppose the answer depends on the situation, there won't be a perfect solution, you have hit on some of the options, but basically tell the climber to hang on while you sort it out by either.
Using an italian hitch,
Using a waist belay,
putting the unfrozen part of the rope through a spare belay device,
urinating over the frozen bit to thaw it out,
chewing on the frozen bit to thaw it out - not after the previous option,
packing in and going home,
get your thermos out and pour that over the frozen bit,
Basically, do your best in the situation, there isn't going to be a proper solution I don't think.
On another point, I wouldn't recommend walking backwards as a normal way to take slack. It is easy to get pulled off your feet back into the crag and lower the climber a little too fast, especially if you are inexperienced wearing crampons.