The original scene takes place in Chapters Sixteen and Seventeen:
The rat was squealing wildly, but not loudly enough to cover up the sounds drifting from Hagrid’s garden. There was a jumble of indistinct male voices, a silence, and then, without warning, the unmistakable swish and thud of an axe.
Hermione swayed on the spot.
“They did it!” she whispered to Harry. “I’d — don’t believe it — they did it!”
Harry’s mind had gone blank with shock. The three of them stood transfixed with horror under the Invisibility Cloak. The very last rays of the setting sun were casting a bloody light over the long-shadowed grounds. Then, behind them, they heard a wild howling.
“Hagrid,” Harry muttered. Without thinking about what he was doing, he made to turn back, but both Ron and Hermione seized his arms.
In Chapter Twenty-One when they go back in time, the scene is clarified:
There was a swishing noise, and the thud of an axe. The executioner seemed to have swung it into the fence in anger. And then came the howling, and this time they could hear Hagrid’s words through his sobs.
“Gone! Gone! Bless his little beak, he’s gone! Musta pulled himself free! Beaky, yeh clever boy!”
So Buckbeak hadn’t been killed the first time around either. The swish and thud had actually been the axe hitting the fence, and the howling had actually been Hagrid howling with joy.
As for how Harry could have seen his future self, that is apparently the way that time travel works in this series. Events happen originally in accordance with all time traveling modifications.