You could try the Wordpress function `status_header()` to add the `HTTP/1.1 404 Not Found` header;

So your *Code 2* example would be:

    function rr_404_my_event() {
      global $post;
      if ( is_singular( 'event' ) && !rr_event_should_be_available( $post->ID ) ) {
        global $wp_query;
        $wp_query->set_404();
        status_header(404);
      }
    }
    add_action( 'wp', 'rr_404_my_event' );

This function is for example used in this part:

    function handle_404() {
        ...cut...
        // Guess it's time to 404.
        $wp_query->set_404();
        status_header( 404 );
        nocache_headers();
        ...cut...
    }

from the `wp` class in `/wp-includes/class-wp.php`.

So try using this modified *Code 2* example in addition to your `template_include` code.