Is there a way to automatically display a notification page (some styled "we will be back soon") in case a webserver fails?
How would that work, considering the domain would have to "suddenly" display the content of a different IP address?
Also, considering that the above would not propagate to all DNS instantly anyways, which solutions are there?
Well in most cases this is a load balancer or proxy in front of the webserver that can redirect when the server is unavailable rather than it being handled at a dns level.
You can use redirectable dns services that use a low TTL to reduce propagation times but this is more aimed at geographical redundancy than for a single server.
A much better way to solve this problem is to never need a 'back soon' message by a) make your server more reliable b) setup redundant versions of everything. Using VMs and loadbalancing this is relatively easy to do even with only 2 servers.