There have been several attempts to implement DHCP and DNS servers or Arduino (some of them are listed in this thread on the old forum: http://arduino.cc/forum/index.php/topic,38116.0.html), but none worked for me out of the box with RedFly Wifi shield I'm using. Thanks to all who tried before me as their examples helped me understand what needs to be done. Over the weekend I put together my own code that works as a simple DHCP and DNS server with lease allocation. This may be used in ad-hoc configuration to make Arduino assign dynamic IP addresses and report those based on hostnames captured during DHCP registration. I also included a full example using RedFly shield with DHCP, DNS, and a simple HTTP server.
The examples and the code is available here: DHCP and DNS servers with Arduino - ZeroBrane. There are couple of unresolved issues that I mentioned in the documentation. Feel free to leave a comment or send me an email as I don't regularly monitor this forum.
Paul.