May we see your cloud formation script?
You are probably right concerning elb + autoscaling.
In order to update ami (without cloudformation) I double the
desiredCapacity value of the autoscaling group manually and set it back
once the new instances are status online at the ELB.
A similar tactics might be scriptable/configurable with cloudformation