This filter won’t allow you to modify headers if your site serves cached pages via a plugin or third-party caching system. The cached page will be served before your wp_headers are filtered.

You may be able to add an HTML meta tag with the http-equiv attribute using wp_head() to work around this for certain headers: http://reference.sitepoint.com/html/meta/http-equiv

function gnu_terry_pratchett_meta() {
    if ( WP_CACHE ) {
        echo '<meta http-equiv="X-Clacks-Overhead" content="GNU Terry Pratchett" />';
    }
}
add_action( 'wp_head', 'gnu_terry_pratchett_meta' );

Alternatively, explore setting headers at the server level with .htaccess or similar if you can.

header set X-Clacks-Overhead "GNU Terry Pratchett"