In the worst case, you can never guarantee that an activity worker won't pick up an activity before you kill it.
You should turn the problem around - SWF activites are supposed to be idempotent, i.e., give the same result even if run multiple times for the same input. If you have long running activities (which I assume you do), use heartbeats to let SWF periodically know that your activites are alive and well (If you have short activities, the low activity timeouts themselves should suffice). Now, when a deployment comes and kills an activity worker on one machine, SWF will schedule the killed activities for processing on another machine (because the heartbeat timeout or activity timeout expired!)
If you build your activities with heartbeats (for long running activities and small timeouts for quick activities), you never need to worry about deployments or machine failures because any time an activity worker goes down for whatever reason, SWF will schedule the task to a different worker.
Along these lines, the best way to deploy is to do a staggered deployment - deploy to a section of your hosts at a given point of time, and based on their health, proceed to more sections till all your hosts are upgraded. This will give SWF the space to schedule activities killed by deployments to be scheduled, and help you prevent quickly detectable bugs due to deployments from spreading to the rest of your system.