Cool concept. There's a BIG difference if this is for a one shot or campaign, and I couldn't quite tell from the OP. For a one shot, I'd just use some pre-made characters. Give them physical descriptions, and let the players pick what sounds best. If you feel generous, you could make extras so no one feels "obligated" to take one they don't want.
If you want to do this as an actual campaign, don't figure out what they are; you'll discover it as they do! This will be fairly simple for ability checks to determine ability scores and skills, but pretty tricky for class abilities. For simplicity I'd not use the Feats and Multi-class optional rules, and have the actual ability scores standard across every character. Tell the players that they need to be as descriptive as possible for their actions, since that will help determine what mechanics they're trying to do.
When a character attempts to do something basic (i.e. not a spell or other class ability), you make a secret d20 check against a DC of 7-13. If they succeed, add a +1 to that ability and skill, adding this modifier to future rolls of the same ability or skill. If they fail, add -1 instead (cancelling out as needed). If a skill gets a modifier equal to their proficiency (+5 IIRC) they realize they know the skill. If somehow they get to a negative proficiency value, they learn they've never been good at it (unskilled). The same works for ability scores, with the first to reach +5 getting the highest ability score, the next to reach +4 getting the next highest, etc.
Abilities should probably use a DC: 15 or 20 instead, with only a single success needed. Once a single ability succeeds, immediately eliminate what classes couldn't perform it (unless you allow multi-classing). One the player figures out what class(es) they are, they should be able to attempt other abilities they know the character should be able to do. Spellcasting is even more tricky, since they need to know what spells even exist and how they're cast (v,s,m) to even attempt it, so I'd require an Arcana check to even attempt it. To actually cast a spell would require a spellcasting check, but I'd use the highest ability that has a class with the spell on the list. If later it turns out they're a different type of caster, then chalk it up to random luck on the character's part.