The basic workflow that we at Codeship tell people is test each repository by itself and if that works push to a staging environment.
Once the push into the staging environment is done you restart the last build on an integration test repository that will thoroughly integration test the whole staging system.
When you build service oriented architecture some backwards compatibility for the time that systems are updated are in our opinion the best way. If there are breaking changes treat every part of the infrastructure as a separate api with specific guarantees and just build a v2 api so you can update the clients, but the old ones still work for a while until you can remove the old clients.
Ideally, your projects should be deployable independently from the other ones, to a certain extent. As an example, your API projects should get deployed, then the other ones using that API can be deployed later, be it a few minutes later or even days.
Hopefully I answer part of your question here?
For deployment, "it depends™" but you can certainly do whatever you need to do, always a matter of time and money! :) Your CI server could kick something on your servers. I encourage you to look at the hosted CIs and their documentation.