The cap cans themselves complete part of the circuits. What I'd do is to get the same value caps that will fit inside the empty cans (or on the bases). The cans can be cut open with a tubing cutter, or just by spreading the crimp at the bottom, then pulling the guts out. And yes you need a good dose of heat to melt the solder. Suck/wick out as much as you can, then go around and heat the tabs individually and work them out by wiggling a little as you go around with the iron.
DaveH52