Easiest Solution... Drumm Roll ... git version 2.10.1 (Apple Git-78)
1) git checkout -b localBranchNameThatDoesNotExistInRemote
2) Do your changes , and godo a git commit
3) git push origin localBranchNameThatDoesNotExistInRemote --force
N.B. - The branch you just created in your local environment , and the remote non-existing branch where you are trying to push , must have the same name.