I run large datacenters with thousands of boxes.
I have a little app (written in golang) installed on each box that effectively is a task runner. Tasks can be written to do anything, including apt-get installing software.
If apt-get fails to run, the task fails (context.WithTimeout) and is run again at a later date. No random hacks needed. Everything is built to be idempotent, self-healing and eventually consistent.