My server supports SNI, so that’s okay.
In the last paragraph you’ve got my problem. There can be indeed as many subdomains as users (and they are dynamically generated). I was already thinking of something like a wildcard, but i did not know that there are special wildcard certs.
Is Letsencrypt also planning to support wildcard certs in the future?