I figured the answer out:
Retrograde analysis is given in Steps 1-6. I need to complete the second half, but I have other priorities to address. I will complete this answer later, if not, tomorrow.
Step 1:
e3$\qquad\qquad\;$g5
For the first two moves, I just put in random moves as mere substitutes. However, in the steps ensuing from this, I would realise these moves were not random and that's how I determined them.
Step 2:
f4$\qquad\qquad\;\;$gxf4
Same ordeal, except I knew that f4 was a certain move because it was provided by the OP. This was when I thought that solving the puzzle would require heaps of trial and error (but soon I would learn otherwise!)
Step 3:
Nh3$\qquad\qquad$fxe3
In this part, the only move that was certain was fxe3. That means there had to be a pawn on the f-file that took an e3 pawn. So one of white's moves was e3, and this had to be in either Step 3 or Step 1.
Step 4:
Rg1$\qquad\qquad$f5
Rg1 was the only certain move, but that meant the rook had to move to g1 where the knight was on! So a knight definitely had to move out before Rg1. This meant the knight would move to h3, f3 or e2 in either Step 3 or Step 1. We already know that e3 is also a move in either Step 3 or Step 1. Now if the knight had to move in Step 1, one of its potential squares to move would be taken out: e2. Note that e2 is only a potential square where the knight can move on, if the white pawn on the e-file has moved to e3, because otherwise that pawn instead remains on e2. Therefore, I decided to let e3 be white's move in Step 1 to not limit the Knight's moves. Step 1 complete! I then moved the knight to e2 and guessed that's where it would go for Step 3. Step 3 complete!
Step 5:
Qf3$\qquad\quad\;\;\,$Kf7
Again, I just did random moves.
Step 6 (the big one):
Qxf5+$\qquad\quad$Kg7
Ok, when Qxf5+ was a certain move, I was confused. The only way the queen would escape from her starting position on d1 is by moving through the e2 square. But this was covered with my knight from Step 3! So my knight had to move either to it's other potential squares, h3 or f3. Now the queen also needed to take a pawn on f5 (shown by Qxf5+) and it was not going to do that if the knight was on f3. The knight would be in the way in that scenario! So, for Step 3, the knight had to go to h3. Step 3 truly complete!
But also, the queen could not take f5 in one move, which meant in a previous step, the queen had to move somewhere after the move f5 happens. Since all of white's moves were confirmed in every previous step except Step 5, this meant the queen had to move in Step 5. The squares where the queen could move to in order to get the f5 pawn on its next move would be f3, g4 or h5. Now if the queen moved to h5, this would be checkmate for black (haha!) and if the queen moved to g4, then an existing f5 pawn could easily take that queen (unwise move, queen!), but of course the queen still exists in Step 9. So the queen had to move to f3. That was white's move for Step 5.
Now in Step 3, we have the certain move fxe3. This means we have a pawn on f4 that can take the pawn on f3. This cannot be the black pawn starting on the f-file, because we need that to move to f5 in the following steps. So the pawn that takes e3 had to start on a different file. Now the only way pawns travel to a different file is diagonally; i.e. through taking another piece! Remember how we must have a pawn on f4 to take e3 in the move fxe3? Well, looking back at Step 2, a certain move of white was in fact f4! So this needed to be taken by a pawn in black's following move in that step. This meant black's move in Step 1 was either e5 or g5.
Now in Step 10, a certain move from white is g5, to which a checkmate happens in white's next move. If black moved the e5 pawn in Step 1, then black's g-file pawn might remain where it is towards the checkmate. Since the checkmate looked to be happening near the g5 square, that means the king needs to be involved, but if black's g-file pawn remains where it is, there isn't much space for the king to move anywhere. Now what if the checkmate happens but the king doesn't move anywhere? Well, I found that unlikely considering the move Qxf5+ (again). The "+" means it is a check, and this check is only possible if the king is not in the square it starts off in; i.e. if the king moves in a previous step where that move would have to be f7, because the king has nowhere else to go... but only if we move the f-file pawn! So f5 must happen before Kf7. Now it can't be in Step 1 because that is either e5 or g5, so this becomes black's move in Step 4. Step 4 complete! Therefore black moves to Kf7 in Step 5! Now if we create more space around this area of the board, this makes black's position less secure (because afterwards, the king would have to move to f7 into this space), increasing the chances for checkmate.
So this finally meant that black's first move would most likely be g5. Step 1 complete! Now we need that g5 pawn on f4, so in Step 2, black's move becomes gxf4 (remember that white's previous move in Step 2 was f4). Step 2 complete! Remember that Step 3 is also complete! And remember in Step 4 white moved the rook to g1 after moving the knight in Step 3 (that move is Rg1) and black's move in Step 4 was f5, so Step 4 complete! This reconfirmed that the only opportunity for the king to move to f7 before Qxf5+ was in Step 5 after white's move Qf3 in the same step. Step 5 complete! Now, doing all the steps in this way, we get that the king is in check from Qxf5+ and we want the king to be very unsafe because a checkmate is coming up very quickly in Step 11 (5 steps away!). So black would most likely not block the check with its g8 knight, and black would most likely not move its king back to e8. Since black moved its g-file pawn to g5 in Step 1, this allows the g5 square to be free, which is the king's only other option if it had to move from its check made by the move Qxf5+. Therefore, I let black move the king to g7 (Kg7) for black's move in Step 6, as that is most likely.
Steps 1-6 complete! Too easy! xD
Step 7:
g4$\qquad\qquad\;$exd2+
The only thing that was certain in Step 7 was that black made a check (signified by the +). The queen made a dramatic entrance to near the centre of the board, but it already checked. Would it check again? Well, after black's move in Step 7, the next step in Step 8 from white is Bxd2 (a bishop takes the d2 pawn). If a piece is taken directly after check, that means that piece was responsible for checking the king in the first place. Therefore, black's pawn on d2 checked the king in Step 7. But we already have a white pawn there, so black's move must be exd2+. That solves for black's move in Step 7, but not white's (as of yet) so I made a random move to substitute.
Step 8:
Bxd2$\qquad\quad\;\,$Qe8
Bxd2 was a certain move from white, but not black's move in Step 8. However, in Step 9, black moves Qf7, so it has to move its queen to the f7 square. But up to now, the queen has remained in its starting position on the d8 square, and since the queen cannot move in the path of a knight, it wouldn't be able to reach the f7 square... unless it already moved beforehand! It couldn't have moved in Step 7 because the only uncertain move right now is with regards to white, not black, so the queen had to move in Step 8. Since the only square it could move to was e8, then black's move in Step 8 is Qe8. Step 8 complete!
Step 9:
Nc3$\qquad\qquad$Qf7
This was the only certain step as a whole. Both of these moves were provided by the OP.
Step 10:
g5$\qquad\qquad\;\,$Nh6
White moving to g5 meant the pawn on the g-file (pawn on g2) had to move three squares, but that is preposterous. This meant that the g2 pawn had to move beforehand. The only step for white that was uncertain up to now was in Step 7, so it made sense that in this move, the g2 pawn was moved up. Since that move plus this move of g5 makes up two moves altogether to reach g5, then that meant the g2 pawn had to move two squares to g4 in Step 7. Step 7 complete!
Step 11 (Checkmate!):
gxh6#
All I needed to do was think of a way to checkmate the king in two moves, and soon enough, I figured out that if the pawn was on the h6 square and nothing else but the king could attack it, it would be checkmate. The king could not attack the pawn, however, because it would be defended by the bishop on d2 (remember that bishop got there from move Bxd2 in Step 8), hence why it would suffice as checkmate. The only piece defending that h6 square to attack the pawn if it was there would be black's night on g8. So, I forfeited the knight by moving it to hg (Nh6) and then I let the pawn on g5 take it (gxh6) to make checkmate: gxh6#. Step 11 complete!
Step 1-11 complete!
Voilà! :D
Edit:
Actually, if the g5 pawn made its way to h6, it would open the g-file for the rook on g8 to check the king. If a pawn on h6 checks the king and the rook on g1 checks the king, that makes a double-check. Since the king is being checked in both directions, then the king cannot block or take the pieces checking it (because since there are two pieces, that would require two moves, which goes beyond chess rules). So it would not matter if black's knight on g8 moved to h6 or if black's pawn on h7, because if the latter happened and the pawn on g5 took the pawn on h7, the knight could not attack it anyway because the king is simultaneously being checked by the g1 rook! Black moving it's pawn to h7 directly prior to this checkmate frees a square for the king, but this is guarded by white's queen on f5 (from Step 6 where white moves Qxf5+). So, this is an alternative checkmate:
Also, white's moves e3 in Step 1 and Nh3 in Step 3 can be swapped, and this will result in the same checkmate, so I guess that makes another solution to this puzzle. But I suppose it is a more sensible opening to play e3 first as opposed to Nh3: a golden rule of chess is that knights are developed, remaining around the centre of the board, not the edge where Nh3 is. But with that being said, there is also another alternative checkmate: the knight moves to f6 (Nf6) and the h5 pawn takes that to check the king on that square instead (gxf6).
If the queen moved to f6 (Qf6) and gxf6 took place, it wouldn't be checkmate because this would free the f7 square for the king to move there, and the queen would not be able to guard that square since white's pawn from the move gxf6 would have blocked the queen from doing so.
Additionally, black can move its h7 pawn not one, but two squares and white's h5 pawn can still take that via an en passant. This will nevertheless result in the exact position of the former alternative checkmate!
Now I can officially say "Voilà!"
Great puzzle, Rewan! :P
