STONE: Admit nothing. Say nothing. Let me bury the matter here and now. No starship captain has ever stood trial before, and I don't want you to be the first.
Stone says "starship" captain; he's not including lesser "spaceship" captains. At the time, Stone's chart only shows 10 Starships in service, and a few months later, Kirk says there's only 12 like her in the fleet. Starships only make up a small portion of the Starfleet fleet, so, the pool of candidates is fairly small.
Also, the "bury the matter" seems to be a way to avoid the court martial in the past where other captains plead out before any official court martial. Even Ron Tracy won't face a court martial if he simply pleads out (temporary insanity) before a trial.
Unless he meant a Captain court martialed on criminal charges involving the negligent death of a fellow officer. But even then - Starfleet is well over a century old by even that point. Kirk's the first ever? Eh.
The first mention of Starfleet by both production order and stardate was in
Court Martial itself. By airdate, it was in
The Menagerie, Part 1. In either case, the concept of the Federation did not exist, only "Earth", "United Earth" and "UESPA".
As for the age of Starfleet itself, in
A Taste of Armageddon, the USS Valiant was destroyed 50 years prior, but Spock says it was an "Earth expedition" at the time, not connected to Starfleet nor the Federation. Fox says, "Captain, in the past twenty years, thousands of lives have been lost in this quadrant. Lives that could have been saved if the Federation had a treaty port here." I think this implies that the Federation existed 20 years ago, but no connection to Starfleet in this episode.
In TWOK, Carol Marcus says Starfleet has kept the peace for a hundred years, so this could be the creation of Starfleet, or just the time to the last major war (is she referring to the Earth-Romulan War referenced in
Balance of Terror?).
I conclude that Starfleet has existed at least a hundred years, but it was under the United Earth. My theory: Starfleet transitions to be under the Federation (UFP) before the first season of TOS (stardate 0000.0 by any chance?), but the reassignment of Earth's space assets (starships/spaceship/starbases/colonies/outposts) are still in committee. By stardate 3030, Earth's starbases/colonies/outposts are moved under the Federation, and around 3115, the transition is complete with the reassignment of starships/spaceships now directly under Federation control. Prior to this, Kirk (i.e. the Enterprise and Starfleet) may have represented the Federation, but through the United Earth middleman. Just after
Tomorrow is Yesterday, the United Earth middleman is removed. YMMV

.