¿Cómo añado cabeceras no-cache a todas las páginas 404 servidas por apache y nginx?

También puedes hacerlo así :

map $status $cache_header {
    default <for_other_codes>;
    404     "no-cache";
}

server {

    [ ... ]

    add_header "Cache-Control" $cache_header always;

}

En apache 2.4, podrías intentar algo como:

FileETag None
<IfModule mod_headers.c>
    Header always unset ETag "expr=%{REQUEST_STATUS} == 404"
    Header always set Cache-Control "max-age=0, no-cache, no-store, must-revalidate" "expr=%{REQUEST_STATUS} == 404"
    Header always set Pragma "no-cache" "expr=%{REQUEST_STATUS} == 404"
    Header always set Expires "Wed, 11 Jan 1984 05:00:00 GMT" "expr=%{REQUEST_STATUS} == 404"
</IfModule>

En always es importante porque este es un:

Está añadiendo una cabecera a una respuesta no satisfactoria (no-2xx) generada localmente, como una redirección, en cuyo caso sólo se utiliza la tabla correspondiente a always en la respuesta final.

Usted dijo que todos los 404s, pero para una referencia completa, por supuesto, podría tener sentido para envolver que en un <FilesMatch> o <LocationMatch> para limitar el alcance.

Creo que esta es una nueva capacidad en apache 2.4 como el uso de expr condicionales no está en la versión 2.2 de la documentación de mod_headers.

curl -I [foo] sin esta configuración:

HTTP/1.1 404 Not Found
Date: Thu, 24 May 2018 17:44:29 GMT
Server: Apache/2.4.18 (Ubuntu)
Content-Type: text/html; charset=iso-8859-1

curl -I [foo] prueba con esta configuración:

HTTP/1.1 404 Not Found
Date: Thu, 24 May 2018 17:44:42 GMT
Server: Apache/2.4.18 (Ubuntu)
Cache-Control: max-age=0, no-cache, no-store, must-revalidate
Pragma: no-cache
Expires: Wed, 11 Jan 1984 05:00:00 GMT
Content-Type: text/html; charset=iso-8859-1

Fuentes:

http://httpd.apache.org/docs/current/mod/mod_headers.html

Mis cinco centavos sobre el tema -

en nuestro proyecto PHP tenemos algunas páginas 404, así que decidí hacerlo a nivel PHP usando las funciones PHP header()