How about a git alias? Set one up to create the branch, and push immediately with the remote branch name you want. Your local and remote branch names can be separate parameters. Something along the lines of

git config --global alias.newbranch '!f() { git checkout -b "$1" && git push -u origin "$1:$2"; }; f'

And then you use it with git newbranch local-branch-name remote-branch-name