Monitoring immutable infrastructure virtual machines
I've looked a bit at Consul and Prometheus and am thinking that that is the way forward?


In short, yes.

Consul is designed exactly for this - it will run health checks against all of your services that you define and can detect when things go down. However, what it does not do it alert when things do go down, it is more designed for automatically taking things out of circulation when they are unhealthy. But it does give you a single point you can query for the health of your infrastructure which you can then alert on manually somehow or combine it with consul-alerts to do this for you.

Prometheus is geared towards metrics and can monitor the health of your applications in ways that consul is not really well suited. It has its only able to alert when defined events occur and you can tune it to monitor exactly what you require.

You might also want to consider external checks like what services such as panopta offer  (this is just an example, there are many alternatives out there) to check public endpoints to make sure they are still working from an external perspective.