ERC721 design for having users pay gas for minting specific tokens?

I'm trying to build an ERC721 token where I generate specific token IDs that contain the metadata itself within the 256 bits. I want to generate 10,000 of these tokens to give away to users.

The easy way would be to deploy the contract, mint the specific token IDs as an admin, and then transfer them to users as they request them. However, the big issue appears to be crazy gas costs. I'm looking for advice on how to go about doing this without incurring huge costs upfront.

Ideally, I want the users to be able to pay the gas fees of minting these specific 10k tokens. However, since I need to be able to generate specific token IDs, how can I ensure that they only generate one from the 10,000 valid ones?

One idea would be to embed the list of 10k ids into the contract. When a user tries to mint a token, it picks the next one from the list. That unfortunately would exceed the contract size limit.

A second approach would be to have a mapping going from valid tokens to a true value. As an admin, I would just initialize this mapping after deployment with all 10k IDs. This is still pretty expensive though since the cost is linear in the number of entries to create.

The final alternative would be to allow users to mint any token ID they want, but require signed requests from my private key. That way I can have a server that signs requests only when one of the 10k valid token id's are picked. If a user requests an invalid token, the server doesn't sign it, and the contract won't accept the request to mint.

The final option seems like a good fit, but I haven't found any good examples of how to do this in code. Are there any resources on this? Does anyone have experience building something along these lines?