tl;dr: There is no reason to assume that a fleet of ships must exist to have people in the rank of "admiral".
Out-of universe, the depiction of the organization Starfleet was inspired by the U.S. Navy. This included duplicating the rank system that seems to be in use there, as well as a random selection of other customs when the situation seemed fitting.
In universe, however, there is no reason to assume that Starfleet must be a total copy of the current navy. As could be seen through the shows, Starfleet's rank structure was mostly used as a hierarchy that primarily indicated command priority and less so fixed positions. The commanding officer of an individually operating Starfleet spacecraft often holds the rank of Captain, but sometimes also Commander or Admiral. The first officer often is a Commander, but sometimes also a Lieutenant Commander or a Captain. And so on. Along these lines, an Admiral is simply a member of Starfleet occupying a higher rank than a Commodore, without any implications of having to have an active fleet.
Even if early Starfleet did not have any ships (which does not need to be the case; they may well have sublight or low-warp ships, just not interstellar explorers capable of reaching warp 5), there is no issue. Given the huge undertaking that starting to bridge interplanetary distances is, an organization needs a setup phase. In that phase, much preliminary work already needs to be done, and with Starfleet being a research organization with some military undertones, all the staff at that time already needs to be organized in a ranking structure. It may be comparable with a newly founded enterprise that has yet to finish the design of their very first product (still living on the initial fund, for instance) and already has a CEO or a director - probably even a marketing director, even though the company is not actively selling anything yet.
To reiterate, and explicitly answer the question:
How did Starfleet build its command structure and flag officers if no one has "boldly been there before?"
Starfleet copied the rank structure (maybe "rank sequence" is a less misleading term?) of the current U.S. Navy. It then started employing people, and based on their successful contributions to the organization, they got promoted step by step through those ranks, starting as Ensigns, and gradually moving towards the rank of an Admiral.