結論
人によって原因は違うと思うのですが、
僕の場合はインスタンスのサイズが小さすぎて、
（デプロイしたタイミングで）nokogiriをインストール時に
（多分）メモリが足りなくて落ちていました。
なので、インスタンスタイプを大きくすると解決しました。
（私の場合はt2.smallで無事動きました。）
参考：
https://stackoverflow.com/questions/25963315/nokogiri-installation-failes-on-elastic-beanstalk
Don't try to run ruby on anything smaller than a t2.small.
挙動
テスト環境として使っていたため、
費用を抑えるため、
インスタンスタイプにt2.nanoを使用しており、
その状態ではbundle installでコケてました。
しかもアプリにリクエストを送ると
クライアントにはcorsエラーが表示されてました。
サーバ内エラーが出てる時に
とりあえずcorsだすのやめて欲しい。
私の場合は、
t2.smallにインスタンスタイプを設定すると動きました。
それ以外にも原因はあるかもですが、
・本番では動いてるのにテスト環境では動かない
・環境によってnokogiriが原因で落ちる時がある
といった場合は一度インスタンスタイプを確認してみてください。
終わり
何か間違ってることなどがあればご指摘いただけると幸いです。