It most probably isn't the same shield.
You are correct the original shield was destroyed beyond repair.
Dunk just bought the gallows shield in Stoney Sept because he was getting a good deal for it.
Dunk limiting his shield and slipped it onto his arm. It was an old
thing, tall and heavy, kite-shaped, made of pine and rimmed with iron.
He had bought it in Stoney Sept to replace the shield the Longinch
had hacked to splinters when they fought. Dunk had not had time to
have it painted with his elm and shooting star, so it still bore the
arms of its last owner: a hanged man swinging grim and gray beneath a
gallows tree. It was not a sigil that he would have chosen for
himself, but the shield had come cheap.
As evident, it was only painted in the way it was at the time of purchase because Duncan didn't have the time to get it repainted with his own sigil.
He said so much later as well:
"Every robber knight I've ever hanged has said the same. Your device
may be prophetic, ser…if ser you are. A gallows and a hanged man.
These are your arms?"
"No, m'lord. I need to have the shield repainted."
So Dunk must have gotten his shield replaced/repainted at any time between his adventures in Mystery Knight to the point he became Lord Commander of the Kingsguard. By Law, every knight must have his own sigil which can be carried on only by his legitimate sons. So Duncan couldn't have used that gallows sigil longer than required. From The Hedge Knight:
The prince nodded at the battered shield Dunk carried, and the winged
chalice upon its face. "By law, only a trueborn son is entitled to
inherit a knight's arms. You must needs find a new device, ser, a
sigil of your own."
Nevertheless, every Knight must have almost as many shields destroyed as the horses lost under him. If someone makes it till the end of his days with an intact first shield, he's either very good or terribly bad.
As for did Brienne actually see Duncan's shield, probably. The shield had the same sigil as Dunk's shield, that's all we know.
The captain's sister found her in the common room, drinking a cup of
milk and honey with three raw eggs mixed in. "You did beautifully,"
she said, when the woman showed her the freshly painted shield. It was
more a picture than a proper coat of arms, and the sight of it took
her back through the long years, to the cool dark of her father's
armory. She remembered how she'd run her fingertips across the cracked
and fading paint, over the green leaves of the tree, and along the
path of the falling star.