He got the suit in the Gallifreyan barn, when he made his plan of action.
I wondered about exactly the same thing. The only possible solution is that he got the black coat on Gallifrey. And I've made a sizeable collection of screenshots to pinpoint the time when he gets it: while he's 'sulking' in the barn on Gallifrey.
In Face the Raven, he's wearing the same velvet outfit as in Heaven Sent:
And he's still wearing it after he emerges from the confession dial onto Gallifrey at the end of Heaven Sent:
In Hell Bent, he still has the velvet jacket when he's lying on a bunk inside the barn with that grim look on his face:
He gets up in his shirtsleeves to see the General with a platoon of soldiers, and immediately goes back inside. While the General reports back to Rassilon, we see a shot of the Doctor dressing himself in the black jacket for the first time:
He's wearing it when the Gallifreyan bigwigs with their silly hats bow to him, and still wearing it when he goes out to meet Rassilon.
As for why he changes his coat, he answers that question himself during Hell Bent:
CLARA: What happened to your coat? The velvety coat. I liked that one, it was it was very Doctor-y.
DOCTOR: I changed it.
DOCTOR: Well, I can't be the Doctor all the time.
Presumably he decided on this black coat and put it on when he decided on his plan of action. Seizing control of Gallifrey in a military coup, murdering the man who helped him do so, and venturing back into the dreaded Cloisters was a very cool, very dark, and very un-Doctory way to proceed, and he wanted to look the part.