Google先生に聞いて見つけた解決法がどれもだめだったので、1つのケースとしてメモ的に残しておこうかと。
Ubuntuなどで、デフォルトのPythonとは違うPythonをインストールし、update-alternatives でデフォルトを変更した場合、apt updateを実行すると、標題のような
ModuleNotFoundError: No module named 'apt_pkg'
が表示されてうまくいかないことがあります。
例えば、Python3.6 が標準のときにpython3.8を入れて切り替えたようなときですね。
検索でよくみつかるのは/usr/lib/python3 の apt_pkg関係の .so をシンボリックリンクで、という解決法ですが、これでうまくいかなかったので、(たぶん相当怪しい)力技で解決しました。
例に挙げたように、システム標準はpython3.6 で、python3.8 を追加インストール、update-alternatives でpython3 がpython3.8 になっているような状況とします。
sudo vi /usr/lib/python3/dist-packages/CommandNotFound/db/creator.py
sudo vi /usr/lib/cnf-update-db
上記の2つをファイルをお好みのエディタで開き、1行目の
/usr/bin/python3 を /usr/bin/python3.6に書き換えて保存する。
私の環境ではこれであっさりapt updateが通るようになりました。
OSはUbuntu 18.04LTSで、別のサーバのほうは素直に20.04LTSに上げたら標準が3.8になったわけですが、この問題が発生した方はちょっとクリティカルな運用があるのでぎりぎりまで引っ張ろうかと粘って思わぬ罠に…