結論
git init した直後に push できない場合は、--allow-unrelated-histories オプションをつけて merge してから push する。
どういう経緯だったか
1. ローカルレポジトリを新しく作った
ローカルレポジトリを新しく作成し、最初の commit を行います。
$ git init
$ git add .
$ git commit -m 'initial commit'
2. GitHub 上でリモートレポジトリを作った
ローカルレポジトリと同じ名前のリモートレポジトリを、GitHub 上で新しく作ります。このとき .gitignore を追加します。
3. エラーが出て push できない
ローカルレポジトリにリモートレポジトリを登録します。
$ git remote add origin https://github.com/hajime-f/sample.git
この後 push したら次のようなエラーが返ってきました。
$ git push origin master
To https://github.com/hajime-f/sample.git
! [rejected] master -> master (fetch first)
error: failed to push some refs to 'https://github.com/hajime-f/sample.git'
hint: Updates were rejected because the remote contains work that you do
hint: not have locally. This is usually caused by another repository pushing
hint: to the same ref. You may want to first integrate the remote changes
hint: (e.g., 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.
エラーメッセージで言われたとおりに pull したら、今度は次のようなエラーが返ってきて pull できませんでした。
$ git pull origin master
From https://github.com/hajime-f/sample
* branch master -> FETCH_HEAD
fatal: refusing to merge unrelated histories
4. --allow-unrelated-histories オプションで merge したら push できた
--allow-unrelated-histories オプションをつけて merge します。
$ git merge --allow-unrelated-histories origin/master
Merge made by the 'recursive' strategy.
.gitignore | 129 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 129 insertions(+)
create mode 100644 .gitignore
すると、正しく push できました。
$ git push origin master
...
remote: Resolving deltas: 100% (2170/2170), done.
To https://github.com/hajime-f/sample.git
f86aa3c..1a66967 master -> master
なにが原因だったか
共通のオリジナル（履歴）から分岐したブランチが存在し、これらが pull によって merge されるのが通常です。
しかし、今回のように git init した直後では、ローカルとリモートで共通のオリジナルが存在しないので、デフォルトでは merge が機能しません。そのため、pull すると「unrelated histories」とエラーが出てしまいます。
そこで、--allow-unrelated-histories オプションで**「こまけぇこたぁいいんだよ！」**と叱咤すれば merge できます。