結論

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 できます。