Having new machines for each deploy is a good idea. Specially if you are a PCI compliant company and refresh your machines like this every week, it eliminates lots of auditing criteria that simplifies your infrastructure significantly. The easier way to do this is to create a new AutoScaling group for a new deploy. The new machines launch in the new auto-scaling group. The auto-scaling group can be attached to ELBs of your choice. Then make sure your health-check to be an endpoint that ELB hits on each server. That endpoint responds with 200 if the server is ready/able to respond to requests. Once ready, they will automatically start serving traffic and you only have to kill the autoscaling group which was created by older deploy to kill the machines and remove them from ELB. There are 2 serious issues to consider which both relate to the machine being stateless:
Graceful termination of machines: you need to make sure the process serving web requests dies after it finishes responding to any established client connection otherwise the user will see a 50x error code; also if you are forwarding your logs somewhere like syslog, splunk, sumologix, you also need to make sure those are forwarded before you terminate the instance;
To not have sticky sessions/session affinity. If you are storing user sessions for web application on these servers locally, you probably have sticky sessions. It is generally a bad idea because now each machine has a state and the load may not be balanced evenly. So, use a central/shared location for session store like reddis/memcache and disable sticky sessions;
Once the above two are implemented, your method of deployment will be cleanest.