Ideally you should consider the Let’s Encrypt certificate and private keys as part of your config for continuous deployment, rather than as part of the application state. For instance, wherever you store things like your database password, you should also store your certificates and keys. That way you don’t need to reissue on deployment.
Unfortunately, this means that the out-of-the-box ease of use of Certbot doesn’t work as well. My recommendation would be to have one stable VM that is responsible for issuing and renewing certificates, and pushing them to your configuration store. The DNS challenge will probably work a lot better for this than the HTTP-01 or TLS-SNI-01 challenges.
This is definitely a type of configuration that is fairly common, but how to do it well is under-documented, in part because everyone’s deployment system is different. Once you get things working to your satisfaction, it would be a great service to the community if you would blog about how you set it up! Eventually I would like to have some documentation on letsencrypt.org about this type of configuration, but I don’t have a good enough idea of what deployment systems are popular, and what people’s needs and constraints are.