Dynamically identify who can mint an ERC721 token

I have an interesting problem that I can't seem to find an excellent solution for.

I have an existing centralized web application. I want to be able to reward particular members with a free NFT token mint. The issue is, I do not have these users' wallet addresses beforehand, and I would love for the mint to happen in real-time. Whether or not the user would be eligible to mint on my smart contract would be determined by my centralized backend system.

Initially, I thought using Merkle Trees might be a good solution. The issue with merkle trees is you need to know exactly which users can mint ahead of time. I don't have these users' wallet addresses, and I don't know who will want to mint, etc. I am almost sure that updating the merkle tree in real-time won't be effective. A single proof is a failure point as it can be easily shared.

This seems like it might become a more common problem as more web2 apps start adopting web3. Has anyone dealt with a similar issue? What are some possible solutions I can explore? I thought of verifying a user, then adding their address to a whitelist, but that will cost a lot of gas. Also, if I batch update every hour, then it isn't real-time for the users. So there are drawbacks. Not sure there's another way of going about it.

Thanks for any suggestions!