Q:

Non-fast-forward error when pushing to git

I'm getting a non-fast-forward error when trying to push to a wordpress git repo, but pulling like the error message says gives me a message that everything is up to date.  This is right after a pull, merge, and commit.  Here is my log: http://pastebin.com/6M4qLqjG
In short, I try to push: 
ajh$ git push staging master

and I get this error, telling me to pull first:
To git@git.wpengine.com:staging/gordo.git
 ! [rejected]        master -> master (non-fast-forward)
error: failed to push some refs to 'git@git.wpengine.com:staging/gordo.git'
hint: Updates were rejected because a pushed branch tip is behind its remote
hint: counterpart. Check out this branch and integrate the remote changes
hint: (e.g. 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.

But if I try to pull, it will say it's up to date:
ajh$ git pull staging master
From git.wpengine.com:staging/gordo
 * branch            master     -> FETCH_HEAD
Already up-to-date.

And this will loop, don't know what is going on.  Any ideas what I can do to git my repo and local lined up?  I've never seen this non-fast-forward error before, not sure what to make of this.  It is also telling me to checkout the master, but I just pulled and merged with master so I don't think I should try that again.
=========edit with fix============
Here is a pastebin with the terminal commands I used to get things pushed properly.  I could still use explanation on what exactly is going on though.  I can duplicate these steps but I don't really understand why they work and the regular push/pull didn't.
http://pastebin.com/u9DAiU5P
Basically I created a new branch, checked out from master, and it fast-forwarded me.  Something weird going on where I have to push to do git push staging staging, the branches on this are confusing

A:

I looked at your second pastebin link and I see a lot of confusion (not surprising since git's terminology seems almost deliberately confusing).
I think the best bet here is to step back and take a look at git terminology first, with some examples from the pastebin.
Let's start with "remote".
What is a remote?
A remote is just a name, like origin or staging or upstream, that provides git (and you) a short name for the full URL of a counterpart git repository.  But git takes advantage of this short name to give you "remote-tracking branches", which we can't describe yet.  First we need to talk about "branches".
What is a branch?
Here's a bit from the pastebin:
1.      The-Dorfchester:gordo.dev ajh$ git checkout -b trouble
2.      M       .idea/workspace.xml
3.      M       wp-content/themes/goTheme2015/blog-loadMore.php
4.      M       wp-content/themes/goTheme2015/home.php
5.      M       wp-content/themes/goTheme2015/stylesheets/layout.css
6.      M       wp-content/themes/goTheme2015/stylesheets/layout.scss
7.      Switched to a new branch 'trouble'
8.      The-Dorfchester:gordo.dev ajh$ git push trouble
9.      warning: push.default is unset; ...

At line 1, you've created a new branch name, trouble.
In git, the word "branch" has at least two distinct meanings.1  There are branch names, like trouble, and then there are sequences in the graph of commits stored in the repository, which form actual branches.  To distinguish these from branch names, let's call them "commit graph fragments".  Since these are unwieldy terms, let's note that the commit graph is, technically speaking, a Directed Acyclic Graph or "DAG".  A piece of this graph is therefore a "DAGlet".2
DAGlets matter because this complaint from git:
 ! [rejected]        master -> master (non-fast-forward)

happens when you're asking git to do a push that will "forget" part of a DAG, i.e., will "lose a DAGlet".  We'll get back to this later.
Branches vs commits
I'm going to assume you have a reasonable notion of "a commit", which in git, saves a complete snapshot of your work—more precisely, a copy of whatever is in the "index" or "staging area"—along with a commit message, your name and email, and the time you make the commit.  They have one more thing that's very important, though, which we'll get to in the next section.
Let's take a look at lines 2-7 now.  When you did this git checkout -b trouble, git noted that it was retaining a bunch of modified-and-not-committed files as modified-and-not-committed.
I know you're trying to do a git push, and git push pushes commits, not files.  So if you have modified but uncommitted files, those uncommitted changes cannot be pushed.
(You don't show a git status in there, but git status is really the best command to use to see what's going on in terms of modified-and-uncommitted files.  It tells you what branch you're on now (which would be trouble here, and if your branch is "tracking" another branch, how far ahead and/or behind your branch is.  Your git checkout -b effectively ran git status for us, though.)
What this means is that at some point, you probably should run git commit to make a new commit.  When you do make a new commit, where does it go?
Commits add to a branch
Whenever you make a new commit, your new commit has that "one more thing" above: it has a parent ID.  For most new commits, the parent ID is "the current commit".  This links the new commit back to one before it, and we can draw that as a little arrow:
A <- B <- C <- D

Here, we start with the most recent (and current) commit, which I'm calling D. D stores the ID of its parent commit C; C stores the ID of its parent B; and B stores the ID of its parent A.
We've just drawn a DAGlet: we pick a starting commit (in this case, D), and that commit gets us a chain of older commits.  If we make a new commit—let's call it E—it will point back to D:
A <- B <- C <- D <- E

and we have a longer DAGlet.
Where does the branch name come in?
A branch name lets us find a specific commit.  That's almost all a branch name is: it's a pointer to a commit.  If you're on branch master and you make a new commit, git starts by finding the current commit—it has a big ugly 40-character SHA-1 "true name", and sometimes you'll see an abbreviated version of this like b66c9f0—and making a new commit from the staging area, your name and email, your commit message, and this parent ID.  Then—this is the tricky part—git writes the new commit's SHA-1 into the branch name.
In this way, the branch itself has grown, and the branch name points to the new "tip commit", at the end of the branch.  If it used to end at D, you now have D <- E with the name master pointing to E instead of D.  Commit E is now "tip-most", and your branch (name) points to E, with the whole chain starting at E forming the branch (DAGlet).  Here's the before-and-after:
[before]
A <- B <- C <- D   <-- master

[after]
A <- B <- C <- D <- E   <-- master

Why does all this matter?
When you go to git push some commit(s), you have your git hand the commits to the other git—the git that listens to the URL stored under the remote—and then ask that git to set its branch to the tip-most commit you're pushing.
Suppose, though, that you ask your git to push your master (commit E) to their side and make their master point to E too.  But—for whatever reason—their master exists now but points to a different commit:
A <- B <- C <- D <- F   <-- master (in their repo)
                 \
                   E   <-- (your proposed replacement)

If their git sets their master in their repo to point to commit E, you'll get them to use the same DAGlet you have: E pointing to D, pointing to C, and so on.  Commit F—the commit they have, that you don't—will be lost.
This is what non-fast-forward means.  It means they have their branch-name pointing to a commit that you don't have in whatever DAGlet you're pushing.  That commit points back to some parents, which point to more parents, and so on.  Eventually—or even immediately—those historical commits join up, but there's at least one commit they have that you don't, that would be lost if they make their branch-name point to (their copy of) your DAGlet.
Review so far:

git push: this needs a remote, i.e., a short name like origin or staging that provides the URL for pushing-to.  That's the first word after push.  Any additional words are "refspecs", which we haven't defined, but for now let's just say they're made up of branch-names (which is mostly true).  You give git a branch name like master or trouble and it tries to push the commits you have under that name, to the remote, using another branch name on the remote.  (Which branch name, on the remote?  Well, we'll see something else on this in a moment.)
The DAGlet you push should simply extend their branch, adding new commits on to it.  Technically speaking, the commit you ask them to set their branch to, should either be the tip commit they already have (this is a "no actual push" situation), or should eventually point back to that commit.  You can add one commit or many, but somewhere in the sequence, one of your new commits has to point back to their existing tip commit.
Or, you can push a branch name that they don't have at all.  If you create the name on the remote, there won't be any commits for it to lose.

Sidebar: push.default
Let's consider line 9, the warning: push.default is unset.  This warning runs all the way through line 28.  This warning comes out every time you run git push with a remote, but with no additional refspec arguments.  To make git shut up, I recommend setting push.default, to either simple or upstream.
You can do this once per repository, or set it in your personal global configuration (where you normally set your user name and email):
$ git config --global push.default simple

for instance.
If you do use simple, git will push your current branch (e.g., trouble) to the remote, asking the remote to update its trouble.  That is, these pushes work by branch names and simple demands that the two different gits here (yours, on your system, and theirs, on the remote system) use the same branch name.
This answers the question "which branch name does your git ask their git to update": if you're pushing branch trouble, your git will ask their git to update their branch named trouble.  If your git is pushing your master, it will ask that their git update their master.  The branch you'll push, if you don't name a branch, is your current branch, and there's no tricky stuff like having a branch in your repository that's spelled Raymond-Luxury-Yacht, but on the remote, it's spelled Throatwobbler-Mangrove.
That's pretty simple, and that is why this is called simple.  There are four other options but I'll leave them out for this posting.
What went wrong here?
Consider lines 35–37:
35.     The-Dorfchester:gordo.dev ajh$ git push trouble trouble
36.     fatal: 'trouble' does not appear to be a git repository
37.     fatal: Could not read from remote repository.

The git push command takes a remote as its first word after push.  The word trouble, treated as a remote, doesn't work (you don't have a remote named trouble).  The push code is full of historical baggage so it tried to use trouble as a URL after that, and that didn't work either.
(I'm going to skip the git show-branch output as something has mangled it, deleting leading white space, making it too hard to read.)
git checkout, and what went wrong here
Git's checkout command is (in my opinion) unnecessarily complex as it has too many modes of operation.  It would be less confusing if git used separate commands for "switch to a different branch" vs "check specific files out of some branch, without changing the current branch".  But these are all lumped into one git checkout command, so let's look at lines 75–79:
75.     The-Dorfchester:gordo.dev ajh$ git checkout staging master
76.     error: pathspec 'staging' did not match any file(s) known to git.
77.     error: pathspec 'master' did not match any file(s) known to git.
78.     The-Dorfchester:gordo.dev ajh$ git checkout staging
79.     error: pathspec 'staging' did not match any file(s) known to git.

The more common form of checkout is git checkout branch-name, but in this case, you're invoking a different git checkout, which is git checkout [ branch-name ] [ -- ] path1 path2 ... pathN, but you can leave out the --.  Since staging is not a valid branch name, it's interpreted as a path instead.  (It doesn't matter that master is a valid branch name, because staging was in the only argument-position where git checkout allows a branch name.)
On line 80 you got a different error:
80.     The-Dorfchester:gordo.dev ajh$ git checkout master
81.     error: Your local changes to the following files would be overwritten by checkout:
82.             .idea/workspace.xml
83.             wp-content/themes/goTheme2015/blog-loadMore.php
84.             wp-content/themes/goTheme2015/home.php
85.             wp-content/themes/goTheme2015/stylesheets/layout.css
86.             wp-content/themes/goTheme2015/stylesheets/layout.scss
87.     Please, commit your changes or stash them before you can switch branches.

You're currently (still) on branch trouble and you asked git to move to branch master.  To move from one branch to another, git must replace the contents of some files in your work-tree.  Which files?
The answer to that is a bit complicated, but in this case, the errors occur for (at least) some files like .idea/workspace.xml that (1) are stored on the most recent commit in the current branch; (2) are in the new branch's tip commit as well; and (3) the contents of that file in the new branch are different from the contents of that file in the current commit.
If the file in the work-tree matched the file in the current commit, git would feel safe in wiping out the work-tree version and replacing it with the switch-to branch (master, in this case) tip commit version.  But these files in your work-tree don't match the current commit.  We saw that in the original git checkout -b when it ran git status.
So, git refused to change branches, requesting that you either commit your changed files, or use git stash to commit them (the difference is that git stash commits them on no branch, rather than on the current branch).
OK, so you finally committed them
Now we get to lines 89–91:
89.     The-Dorfchester:gordo.dev ajh$ git commit -am "idk"
90.     [trouble 820decb] idk
91.      5 files changed, 39 insertions(+), 93 deletions(-)

This made a new commit, on the current branch trouble.  It then moved the branch to point to the new commit, whose 40-character SHA-1 starts with 820decb.
Now we hit line 92:
92.     The-Dorfchester:gordo.dev ajh$ git push master

This asks your git to push to the remote named master.  There isn't one, and you get the same error as earlier.  All of these also spit out that enormous annoying "set your push.default" message, which gets us to line 119, and also 125:
119.    The-Dorfchester:gordo.dev ajh$ git pull master
...
125.    The-Dorfchester:gordo.dev ajh$ git push --set-upstream master trouble

These both have the same problem as before: the word master is in the slot for a remote name, but isn't a valid remote.
This brings us to line 131:
131.    The-Dorfchester:gordo.dev ajh$ git push --set-upstream staging trouble

Finally, a command git likes! :-)  This time staging is in the slot for a remote, and trouble is in the slot for a "refspec", and both of those work.  (The --set-upstream tells git push that once the push succeeds, it should record staging's trouble as the "upstream branch" for your local staging.  For a lot of words on what this all means, see this answer.)
Let's skip one more wrong checkout and proceed to line 154 (and its attendant success messages):
154.    The-Dorfchester:gordo.dev ajh$ git checkout master
155.    Switched to branch 'master'
156.    Your branch is behind 'staging/master' by 16 commits, and can be fast-forwarded.
157.      (use "git pull" to update your local branch)

This one works.  It's not because of the successful git push, though: it succeeds this time because you finally committed on your trouble branch.  That got the modified files safely stored inside the repository, as that new commit whose 40-character "true name" SHA-1 ID starts with 820decb.
Once they were committed, so that your work-tree was clean, git would have been fine with git checkout master.  You also pushed your trouble to your remote named "staging", giving it the name trouble there as well, but that's not important for the git checkout master step.
Line 155 acknowledges the success.  Line 156 is the output from git status, telling you that your master is behind its upstream (which your git calls staging/master) by 16 commits—there are 16 commits they had that you didn't—and is not "ahead of" its upstream.  Again, see my other answer (already linked above) for more on this.
You then ran git pull, which is really just git fetch followed by git merge (it's meant as a convenience wrapper for these two steps, but it turns out the second is the wrong step for most people, so it's configurable).  The git merge did a "fast forward" merge, which means you had no new commits, and they had new commits, so your git was able to just "slide the branch forward" to the new branch-tip, adding their new DAGlet to your existing DAG without any fuss at all.
That gets us all the way to line 388 (and its response lines):
388.    The-Dorfchester:gordo.dev ajh$ git commit -am "pull from staging/master to master, idk"
389.    On branch master
390.    Your branch is up-to-date with 'staging/master'.
391.    nothing to commit, working directory clean

This git commit command found nothing to commit, and did not make any new commits.  Your branch master has no new commits added and the branch tip is the same as it was before.
392.    The-Dorfchester:gordo.dev ajh$ git push master

This is the same error as before: git push wants the name of a remote, first.  The big spew about push.default gets us all the way to:
419.    The-Dorfchester:gordo.dev ajh$ git push staging master

This one is correct, but we just saw that your git commit earlier added no new commits.  So your git calls up the git on staging and finds there's nothing to do:
420.    Everything up-to-date

and it does nothing (and succeeds).
(Incidentally, the big spew about push.default is omitted here because you gave git push both a remote and a refspec.  The push.default setting is what push should do if you don't give a refspec, i.e., if you give it only a remote, or give it nothing at all.  If you give git push nothing at all, it will figure out the remote to use based on the current branch's upstream setting.)

1How many meanings depends on how you count some finer divisions.  See this question for more.
2Be aware that DAGlet is my own invention, so if you start using it, you may have to define it for your audience.

