After trying out a couple things, I realized I could just create the remote branch from master, and just rebase the damn thing:
git push origin {new_remote_branch}
git branch --track {new_remote_branch} origin/{new_remote_branch}
git checkout {new_remote_branch}
git rebase {local_branch}
git push
Not super interesting, but enough and short enough to blog about. tip!