I had the same problem with absolutely same symptoms… I was about to rebuild my whole system in my despair)).
I even was so naive to try git config --global core.askpass "git-gui--askpass"
as some people suggest here, but it didn't work…
git push
was still freeze…
But then I figured out that there was an error with my SSH agent. So I've restarted ssh-agent and… PROFIT
Conclusion: Always check your SSH Agent and SSHD server when you have troubles with ssh connection… I'm pretty sure that was your problem (And that's why it worked after reinstallation of your system)