We are a service provider and a large part of our business is private clouds. I am also in the process of rolling out a new enterprise patch management solution which will handle patching of these private clouds.
The solution that we are using is the first scenario you mentioned patch in-place. We evaluated over a half dozen different patching solutions and I came to the conclusion that patching solutions out there still have not really caught up to the idea of cloud.
I spoke with the vendor or the solution that we choose and being more visualization aware is on their roadmap. The product currently can tell which machines are virtual versus physical. I have submitted a feature request to allow pre-patch VM snapshots to create a fail-back point. Ultimate I would like it if the patching solution could completely manage the VM snapshots both creating and removing them after a specific period of time. This type of cloud awareness and integration is going to be key going forward to leverage the power of the cloud environment.
Until our patching solution becomes more cloud/virtualization aware we will continue to patch systems using the classic model because it still works.