I have somewhat a similar setup allowing me to roll thousands of domains within a specific platform which I have developed.
(Take note that if you'd like to have multiple dynamic subdomain this can accomplished with a wildcard DNS entry *.domain.com pointing to an IP and a ServerAlias in one of your virtualhost *.domain.com - but since this is pretty simple I won't go any further and explain how a setup on dynamic domain can be setup)
I am not going to tell you what is the best way since I believe there is no such things, there are multiple ways to do what you're trying to achieve: I just hope that by shedding some light over my setup, it might help you.
Adding the domain to the DNS server should be automated by some script (I prefer having that functionality in a bash script and keep that separated from PHP or any other language).
The script that take care of everything is too long but the rational is simple:
Add a domain
1. Calculate the Serial number (date + some incremental number)
2. Check if domain exists
3. Validate the IP (if you are going to use multiple IP across your system, if not you can have this bit static)
4. Add to named.conf the domain zone reference
5. Create the zone.db file
Remove a domain
1. Decrease the serial
2. Remove the domain zone reference from named.conf
3. Remove the zone.db file
Since Serverfault doesn't really show bash script in a good manner (and my script is long anyway), I have posted this to pastebin, you can find the script here
Then you need to take care of the virtualhost, it's pretty easy if you're using apache 2.2, you just need to write a script that create a $domain.conf file where all the directive are specified.
The third stage would be to use some kind of RewriteRule that will pass the domain to an index.php where you'll be able to internally redirect that domain to the relevant structure.
I believe in this schema since this is a schema that will allow you to easily do changes and tweaks in the future.
Hope that helped.