You are not going to be able to detect when someone points a DNS entry to your server (be it an A record, a CNAME, or anything else) unless the DNS zone is also being managed by your service.
I would suggest having Apache set to have one vhost that responds to all domain names (that are not explicitly listed for other vhosts) and create a mod_rewrite mapping rule to map the domains to specific directories on the server, i.e.
http://some.domain.tld/ to be service from
That way no Apache configuration changes need to be made for each new domain, you just need to make sure the directory exists. You can automate this by having an intelligent 404 handler that creates the directory the first time it is requested and redirects the browser back - take care though not to make this in such a way as it still reacts to other 404 errors correctly and make sure it properly sanitises its inputs so it can't be used for a DoS attack or to create structures that would make other attacks easier.