In Debian Linux, how can I get a new IP assignment on boot up? I'm working with VMs and I am required that every machine gets a new unique IP after booting up.
It probably depends on your VM configuration, which in turn depends on the VM engine you are using. There are several ways to connect a VM to your network:
have a look at VirtualBox' documentation at http://www.virtualbox.org/manual/ch06.html
Also be sure that all your VM guests have different MAC addresses, or else you will go into big trouble. Especially true if you create your VMs by copying (VirtualBox has a very visible option when duplicating VMs).