If it's complicated to use Spine's Find and Replace tools for the job, it might be easier if you export your skeleton as a JSON and then manipulate that with some code (or pre-existing program) that can juggle JSON, or even plain text if it came down to it.
Then you can reimport the manipulated JSON as needed.
Also, to clarify:
What are in those 50 skins? Are they 50 actual unique sets of swapped images?
Or are you making skins that are just different combinations of a few sets of image parts? Is that why for one new pair of shoes, you have to change a hundred skins?
If you're doing this, you might be better off building a mix-and-match system at runtime, which is pretty simple to do as long as you leave the attachment/alignment data in the skeleton.
