2020年末以前のAll in One SEOだと404ページのタイトルが管理画面から設定できたのですが、
最新のAll in One SEOだとそれができないようです。

▼参考
How do I change the title for the “404” page?

変更できるようになるまで地味に詰まったのでその解決方法についてご紹介します。

結論

header.phpfooter.phpに以下のように書けばOKです!

<!-- 色々省略 -->  

  <?php if (is_404()) : ?>
    <title>ページが見つかりませんでした | <?php echo get_bloginfo('name'); ?></title>
  <?php endif; ?>

<!-- 色々省略 -->

  <?php if(!is_404()):?>
  <?php wp_head(); ?>
  <?php endif;?>

<!-- 色々省略 -->
<!-- 色々省略 -->

<?php if (!is_404()) : ?>
  <?php wp_footer(); ?>
<?php endif; ?>

<!-- 色々省略 -->

解説

以下の記述だけ書けばうまくいく気がするのですが、実際はtitleタグが反映されません。

  <?php if (is_404()) : ?>
    <title>ページが見つかりませんでした | <?php echo get_bloginfo('name'); ?></title>
  <?php endif; ?>

なので、404ページの時のみwp_headとwp_footerを読み込むようにしています。

ただ、こうすると、サイトのcssやjsファイルなども読み込まれないので、別途、functions.phpではなくheader.phpやfooter.phpでcssやjsを読み込む記述をする必要があります。

まとめ

管理画面から設定できるようにしてください。。。
※もしこれ以外で方法知っていましたら教えていただけると幸いです。