There are multiple ways to solve this. Once you understand the pieces involved, you will likely see a clear solution.
A skin is a simple map of name to attachment. The name is the name of a skin placeholder. The attachment is which attachment to actually show for that skin placeholder.
You do not need to create a skin in the Spine editor for every possible combination. Doing that stores the skin in the exported skeleton data, but you can instead can create a skin on the fly and populate it with any attachments you like. See here:
Runtime Skins - Spine Runtimes Guide
The problem you have is not really that you have many skins, but that you have many attachments. One way to define attachments is to create them in the Spine editor. Like skins, doing that stores the attachment in the exported skeleton data. That works fine for many projects, but if you have thousands of attachments it can be tedious to create them all beforehand. Instead you can create them on the fly using conventions. See here:
Runtime Skins - Spine Runtimes Guide: Creating attachments
Once you can create attachments on the fly, you can create a skin with any combination of attachments. The last part is that each attachment needs an image. You could download them but many apps need all the images in the app, so they can be shown to the user to "dress up" their character.
Once you know the attachments you want on the character, you can generate 1) the attachments, 2) a skin containing those attachments, and 3) an atlas containing only those images. To create the atlas, see runtime repacking if you are using spine-unity.
