From what I understood this is more of a deployment issue. The way I see it there are couple options.
If you can deploy SQL Server and application changes simultaneously (or at least near to that) then you can just publish both at the same time but I guess it depends on the system.
Can you do this over the weekend when there is no risk of applications crashing?
Do you deploy the new application version to all users at once? If yes then you can just create new SP first, deploy new application version and then delete old SP.
Anyway, hope this helps. If not, please provide more details on number of servers, number of client applications and such…