The CPU is most definitely not fried if the computer runs and stays running.
Processors are very delicate, 100c CPU could also indicate motherboard problems, but you even said yourself. There's no thermal paste.
Apply thermal paste to the back of the CPU and re-attach the fan ASAP.
FYI...