結論

サポートに連絡して二段階認証を一時的に解除してもらえば解決できます。
私の場合は1週間弱ほどで対応してもらえました。

＜2023/11/26追記＞掲載の情報はXになる前の2023/7頃の情報です。現在は細かい点が違う可能性が高いので、サポートにお問合せください。

＜2024/4/7追記＞「●日待ってもサポートから返事がこない」「やり方がわからない」等のお問い合わせを私（hisana）にいただいても対応できません。すべてX(Twitter)公式へお問い合わせください。あくまで以下は「私の場合はこれで解決ができた」という一例です。

前提

ログインできなくなったアカウントのID・パスワードが判明しており、登録してあるメールアドレスの送受信ができることが前提です。

経緯

（1）新しいPCでTwitterにログインしようとする
（2）二段階認証にひっかかってログインできない
※電話番号で二段階認証していたが、電話番号での認証は課金ユーザのみの機能になったため使えなくなった
（3）別の端末で二段階認証設定を解除しようとログインするとパスワードリセットがかかる
→新規端末でログイン試行して失敗した所為でセキュリティ対策としてパスワードリセットが発動
（4）パスワードをリセットした結果、すべての端末で二段階認証を求められてログインができなくなる

（3）が完全に罠でした。

対処方法

（1）ここからサポートに連絡する

内容は「二段階認証のバックアップコードを紛失してログインできなくなったため、一時的にアカウントの二段階認証を解除してほしい」と送る。

（2）自動返答で的外れな返答（ログインした後の設定変更についての説明）が来るので返信で「二段階認証のバックアップコードを紛失してログインできなくなったため、一時的にアカウントの二段階認証を解除してほしい」と再度送る（1で送ったものと同文で問題ない）

（3）数日（2～3日）経つとサポートから「対象アカウントの所有者であることを確認するためにログインを試してみてくれ」とくるので、ログインを試す（もちろん二段階認証のコードはないのでログインは失敗するがOK）

（4）数日（2～3日）経つとサポートから「二段階認証を一時的に解除したよ」と連絡が来るのでログインできる

Twitter運営が変わってサポートが手薄になったらしいという話があったので対応してもらえるか不安でしたが、きちんと対応してもらえました。
ありがとうTwitter。