How to filter content on Save/Publish to add rel=”nofollow” to all external links?

I would try “wp_insert_post_data” filter.

add_filter('wp_insert_post_data', 'new_content' );
function new_content($content) {    
    preg_match_all('~<a.*>~isU',$content["post_content"],$matches);
    for ( $i = 0; $i <= sizeof($matches[0]); $i++){

        if ( !preg_match( '~nofollow~is',$matches[0][$i]) ){
            $result = trim($matches[0][$i],">");
            $result .= ' rel="nofollow">';
            $content['post_content'] = str_replace($matches[0][$i], $result, $content['post_content']);
        }

    }

    return $content;
}

Obviously needs work, just a PoC.