Git master branch has no upstream branch

The following command worked for me:

git branch --set-upstream-to=origin/master master

Instead of creating a new repository on Github, cloning that, or reinitializing your local repository, the following command would have been sufficient:

git push -u origin master

origin stands for the remote name (default is origin),
master is the branch you want to push, in your case it's master, otherwise you would have to change that in the command.
-u means, that your local branch will be setup to track the new created master branch on the origin repository (the master on the origin will be the upstream branch of your local branch). If the branch master doesn't exist on the remote repository, it will be created, otherwise it will be updated (the -u works no matter if it exists or not).