I have a 94 lumina euro and this winter it was @#$^&#$% cold and I had the SAME symptoms you describe- no fans, high temp, no heat!
I tried alot of the stuff you mentioned- temp sensor, etc. nada
One day I got mad and ripped out the heating/ac control module (little box-controls on the dash where you push the buttons to make it warm
) and got another lil box at my local junkyard for a few bucks, popped it in, and presto, it was fixed, no overheating, fans worked, and it was bloody easy.
Wish I tried it sooner.