The only reason I can imagine you're asking this is you don't have any, can't wait and must get operating.
Scav some thermal pad off an old motherboard or GPU VRM heatsink. Use some silicone grease, the type used in plumbing for instance. Even a tiny dab of toothpaste works better than nothing (but absolute last resort and not really recommended).
Don't use Vaseline (petroleum jelly) as it melts and runs all over pretty badly.
Whichever you use, don't push it hard, and clean it off completely as soon as you get some proper thermal paste in- house.
Why do you need to replace the fan?
If you mean just the fan and not the whole cooler, I do not see why you can't do as you ask.
If you need to remove the cooler itself, then, yes, you need to clean off the old paste ans replace with new.