I have done this several times with different sites.
Yes you will need to have a DNS server to do this or at least an API into another DNS service (I am not sure what is available out there).
In the past I have also handled this manually and just had a quick method of allowing them to request a custom domain. Then if we purchase that domain I forward it on to our DNS servers.
Then the code that I typically write splits the http_host into a list or array and then check to see if the domain portion "example.com" is the standard domain. If not then I look it up in the database to find if it is a custom domain I do all checking in one place or function and return the account id so that the rest of the site doesnt have to worry about whether it is a custom domain at all.
If you have any other questions I would be happy to help you out.