Given that the crux of your question is basically related to accessing newly created sites from users of your site which is designed to allow this, you would indeed need to create virtual hosts for every site created (as otherwise your web server would have no way to determine which site to process requests for).
You could look at automatically creating vhosts based on a template and reloading the nginx config, but I wouldn't recommend it - I generally find that this level of automation is undesirable and that you should really be taking care of individual site configs on a per-user basis.
You would also need to create an appropriate wildcard CNAME record as per this article in your DNS.
Edit: as per the comments below, here is a suggestion as to what you could potentially implement.
You could, for example, have a template virtual host file, containing something similar to the following:
server {
listen 80;
listen 443 ssl;
server_name template.yourdomain.com;
access_log /var/log/nginx/template.yourdomain.com_access.log main;
error_log /var/log/nginx/template.yourdomain.com_error.log warn;
}
Which you could then replicate altering the 'template' entries with the subdomain of the user's choice. It depends on the rest of your environment, but for example you could have a text field to allow them to input the desired subdomain, then have the 'submit' (or similar) action trigger a script you've created to alter the above config file for an appropriate one for them, copying it to theirdomain.yourdomain.com.conf and then running service nginx reload
.
This is just a vague idea of what you would need to do - the specifics are up to you based on your environment and requirements.
As I have already said, however, you should consider the implications of implementing this.