I'd try to figure out what the substance is - is it softish? That would be either hot-melt or silicone. If it's one of those you can either just cut the leads and pull the thing off (neither one will damage the board in the process), or if it's hot-melt you can heat it up a bit and the thing will come right off.
Given that you can't cut it easily, I'm guessing it's hard as a rock. That means either epoxy, or superglue, and of the two I'd guess epoxy. If it were superglue, you could get some remover (yea, they make a chemical that will soften superglue!), but if it's epoxy you've no such luck (the only chemical that would work is pretty carcinogenic and thus not readily available). At that point I'd cut the leads and break the cap off - either chiseling it off, or using a thin bladed saw to cut the epoxy above the board (breaking the cap into pieces if need be).
Then, once you've got the cap off, use silicone or hot melt to attach the new one.