So after much stressing I managed to remove the fan from my Am5x86 using a chisel blade on an x-acto knife. After carefully working the blade under the fan the majority of it broke free. Unfortunately a portion remained stuck to the cpu. I spent about an hour painstakingly scraping the plastic off but I removed enough that I should be able to glue on a new heatsink with thermal paste in the center. Thankfully after all that I was able to power up the system, boot into windows 95 and play SimCity 2000 for about 10 minutes. The cpu never went above 101f with a fan blowing on it, so I'm reasonably confident the heatsink fan combo I have coming in will be more than enough to keep it cool.
Fan removed
The attachment 1fan_removed.jpg is no longer available
Failing fan
The attachment 2bad_fan.jpg is no longer available
Most of the plastic scraped off
The attachment 3most_plastic_removed.jpg is no longer available
Most the old glue cleaned off
The attachment 4removed_most_glue.jpg is no longer available
Testing that the cpu still works
The attachment 5desk_fan.jpg is no longer available