Add the following line to the config file in your .git folder (or to your global git config) to auto push a new branch you've created locally:

[push]
    autoSetupRemote = true

Now, on the first time you enter git push for a new branch your terminal won't complain that the remote doesn't exist, it just pushes your branch.