How to force a 404 on WordPress

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.