Earlier version 3 of the ISC DHCP distribution can do dynamic updates of DNS based on the hostname that the client wants. However, the "hows" of this integration have not been entirely worked out at this time, so I'll refrain from teasing you with what you can't do.
The DNS update conditionals have this purposethey allow the DHCP server to specify update conditions to the DNS server, such as "if the name already is in use" to forbid users from using new names, or "if the name is not present" to forbid users from using names already in use. Which way you want it to go is a pure administrative decision, and what you think you can allow depends on how much you trust your users. If you don't trust your users, however, I recommend that you give them static names.