後藤です。
返信ありがとうございます。

> InnoDB のネクストキーロックによるものだと思います。
> 試しに、以下のようにトランザクション分離レベルを変更すると
> デッドロックはおきませんでした。

ネクストキーロックが原因だろうとは思っているのですが、
デッドロックの理由が良くわからないのです。
下記のように考えると REPEATABLE READ でもデッドロックしないように思えるのですが・・・

  [A] SELECT 〜 FOR UPDATE: 最終行と最終行の次のギャップをロック
  [B] SELECT 〜 FOR UPDATE: 最終行と最終行の次のギャップをロックしようとして解放待ち
  [A] INSERT: 既に挿入位置のギャップはロックしているので成功するはず・・・？