I can't help with leather thongs for seats, but getting the old spline out is not really a problem.
Removing the spline that holds machine-woven cane in place is greatly facilitated if you have a 1/8 inch chisel -- a size that is a little unusual, but readily available from mail-order/internet woodworking supply outfits. The groove holding the spline is usually a bit wider than 1/8 inch.
After cutting a bit of the spline away, easily enough done at the end of the spline, the narrow chisel can be inserted under the spline and used to pry it up and out of the groove, and then to clean out the groove.
I've been able to clear the groove just using the chisel and a sharp utility knife. If glue or varnish holding the spline and cane in place are unusually difficult, I suppose heat, moisture, or solvents might help.
The only seats I've seen with leather thongs are seats which had no spline groove, but which were originally drilled for hand-woven cane -- with the leather threaded through the holes, replacing the original cane. I'm not sure how you would install leather on seats with a groove, and no holes.