I was going to suggest mouseguard, but then you elaborated: "I mean class in the DnD v3.5 sense" on chat.
Don't try to hack this into D&D 3.5. You'll run into abstraction problems. If you want a system designed for this level of abstraction try Ars Magica, GURPS, or Mouseguard.
You're operating at the wrong level of granularity, both in action and in consequence to produce characters. While rules exist for level 0 characters in 4e that provides a way for PCs to flesh out their choices in play, the level of control and restriction of agency you propose is far too broad.
Smaller choices
The reason why mouseguard works is that the players make the choices about their characters. However, the choice they make isn't at the "I'm a fighter" or "I'm a pirate 2" level, the choice is "I'm going to solve this problem in this way."
Mouseguard also doesn't dump all sorts of abilities aon a character based on a single roll. Character development requires an extended pattern of actions to determine a facet of character.
In the same way, Ars Magica provides for XP only in the abilities you use. As a note, you can see that both of these are effectively class-less systems, the abstraction of "class" and the abstraction of "fine-grained skill control" go together like chalk and cheese. Classes are designed to abstract away fine-grained skill control.
Larger Scope
Even worse, While skill-granularity is much finer in Mouseguard and in Ars Magica, action granularity is the opposite. In Mouseguard, especially, a single action determines the course of a scene. (Not... entirely true, but functionally true enough.) In Ars Magica, it tends to be (in my game at least) a single roll or spell determines the course for the next 15-20 minutes of game.
If you have to track every swing of a sword... and a combat has thirty of them, go play a computer game.
Granularity of choice and of action matters.
The explicit design of class-based systems concentrates player agency into the large "I'm an x" and the small "I'm going to hit you... again." This concentration is absolutely intentional, becuase it removes the complex eddies of the mid-level granularity where Mouseguard (and to a different degree, Ars Magica) sit. Skill-as-use-development works very well when you have few rolls of important skills. Not many rolls of unimportant abilities.
To quote from a surreal fanfic I'm reading:
But that wasn't the really weird thing. The more Milo watched these students in their classes, the harder a time he had sleeping at night. The way they were learning was wrong. It was oh, so, incredibly wrong. Ordinary people learned in discrete increments: they levelled up, their powers, skills, and abilities increased, and then they plateaued until attaining enough Experience Points to go up another level. It was just obvious. That was, intuitively, the way everyone – Humans, Elves, Dwarves, Kobolds, Mindflayers, small fluffy hamsters, everyone – learned.
Watching his fellow Gryffindors, Milo wondered, though it seemed impossible, if their skills didn't develop gradually. There seemed to be a slow, constant growth in magical ability, historical knowledge, broomstick skills, or whatever, that depended on that student's particular aptitude in that area.
And it is * precisely* this issue that you're struggling with. The level of granularity in your learning and action systems is fundamentally tied to the model of the game. By interfering with this, you significantly diminish player agency.
Mouseguard
This burning wheel derivative presents a character modelling system in such a way that the only way to advance is to fail and pass a roll a number of times. Therefore, the skills you use, and the way you solve problems directly determines how you solve problems. You can certainly get training in something, but that's by taking time to train