Sadly, setting the hostname from DHCP is not trivial in Debian, here is the result of my research into the topic. I found 2 things to be essential and learned both of them by analysing the dhclient script.
1. Set the hostname to localhost
The first thing to do is to set the system hostname to localhost:
# echo localhost >/etc/hostname
2. Workaround for broken dhclient-script
The dhclient-script has (IMHO) a bug: If there is an old DHCP lease with a hostname in the lease database (e.g. in /var/lib/dhcp/dhclient.eth0.leases), then the script will not set the hostname from DHCP even if the system name is still localhost.
To circumvent this bug simply create a dhclient enter hook to unset the old host name variable:
# echo unset old_host_name \
The result is that now the hostname will be always set from DHCP, even if something went wrong or if there are old lease infos.