Wildcard DNS entry. Create an entry for *.example.com that points to your service and let the code figure it out.
Now back to my question. how about user's own domain?
Do they need to set it up or it can be configured on our end?
Google creates such entries if you register a domain through their google app account. How can that be done?
We're currently setting up DNS manually because we don't have that many people using their own domains, but we could easily automate it if it ever became burdensome. We give users the choice to let us host their DNS (and then help them update the nameservers on the domain) or just tell them what IP they need to point their domain to.
If the users own their own domain via a third party, you can not modify their DNS record unless they gives you their account. Or user can transfer domain to you.