In A Feast for Crows Brienne remembers seeing a shield described like the shield Tanselle painted for Duncan in The Hedge Knight.
But later, in The Mystery Knight, Dunk recalls that his former shield has been crushed in a fight, and now he has a shield with another painting that gives him the name "The Gallows Knight".
How can the first shield end up in Lord Selwyn Tarth’s armory if it has been destroyed in a fight?
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.
