I have been thinking about this repair since you first posted it.
From your description it sounds like a nightmare, or what we call a
Pandora’s Box repair. once you start you may be married to this
nightmare for a long, long time.
Unseen, I am hesitant to make too many suggestions, and would want
to examine this piece very closely before touching it.
Basically though, yes, I would want to remove the old prongs, and
drill to fit in new ones, but because of the old low temp solder,
and unknown stones that may not take the heat of the torch, I would
lazer weld the new prongs rather than solder them. Because of the
old solder, even lazer welding has to be done with a degree of
hesitation, and I would want to remove as much of the old solder as
I possibly could before starting to weld.
Some times the very best service you can offer your customer is to
just say NO, this is too far gone to repair correctly, and to put
their money into a new piece that they will be able to wear for years
to come, rather than be constantly afraid the old piece will only get
worse with wear. Fool that I am though, I too often will go ahead and
at least attempt to do such a repair, if the customer truly wants me
to. We both need to know before I start that I am not guaranteeing
results, and that we are exceeding safety margins by trying.