They could produce their parents, or any witness of their birth.
They could (if they were born wealthy) produce a hallmarked silver spoon engraved with their name. Not proof, but persuasive.
They could produce their 21-year-old younger sister, who has government ID (yeah, I know, that is a resort to government ID).
Best of all: they could produce a birth certificate, signed by a doctor (not itself government ID, just a prerequisite to getting a government ID).