If free quarks can't exist, how did the universe form?

In the first stages of the Universe Quarks and Gluons were asymptotically free. This state of matter is called Quark-Gluon Plasma. Then, as the temperature of the Universe kept decreasing, the so-called hadronization (quarks combine to form hadrons) took place.

The coupling constant of the QCD (which, to make it simple, sort of represents the intensity of the strong interaction between quarks) is a $\textit{running coupling}$: it means it's not really a constant, but it varies with the energy scale. As you can see from the picture below, the $\alpha_{QCD}$ decreases at high transferred momentum. This means that quark tends to behave ALMOST as free particles when the energies are really high. You can also view them as a gas of fermions (quarks) and bosons (gluons).

In these conditions ($\alpha \ll 1$), a perturbative approach is possible: we use pQCD (perturbative QCD).

Quark-Gluon Plasma can be obtained nowadays by high energies collisions of heavy-nuclei. This is achieved at CERN, for example, by the ALICE experiment, by means of Pb-Pb collisions at $5.02$ TeV.

"Free quarks can't exist" is simply an oversimplification of the actual situation in quantum chromodynamics (QCD). A better statement is "free quarks cannot exist at low energies", where "low energy" means below the deconfinement scale.

Confinement is precisely the phenomenon that says that the force between two quarks rises linearly with distance, meaning you can never separate two quark, since doing so would require infinite energy. Now, we unfortunately do not have a full theoretical understanding of confinement in continuum QCD, but what we do know - both from heuristic arguments and from lattice computations - is that QCD exhibits a phase transition between a confining phase and a deconfining phase as the energy scale increases.

This is not due to the running coupling as such, but to the expectation value of the order parameter of this phase transition, the Polyakov loop, a variant of the Wilson loop, becoming non-zero. As long as the Polyakov loop is zero, the free energy of a two-quark system is infinite, meaning they cannot be separated. Lattice calculations indeed show that the phase transition to a non-zero Polyakov loop happens as the energy scale increases, so in the early hot universe, free quarks could exist without contradiction to our current situation.

The symmetry which is broken by the Polyakov loop is the so-called "center symmetry" of the gauge theory on the lattice, see this question.

This article in wikipedia clarifies how the universe has evolved as far as our present understanding of particle physics and general relativity goes.

In particular for the strong interactions, the present theory is QCD,which models quarks and their interactions with other particles.

QCD enjoys two peculiar properties:

Confinement, which means that the force between quarks does not diminish as they are separated. Because of this, when you do separate a quark from other quarks, the energy in the gluon field is enough to create another quark pair; they are thus forever bound into hadrons such as the proton and the neutron or the pion and kaon. Although analytically unproven, confinement is widely believed to be true because it explains the consistent failure of free quark searches, and it is easy to demonstrate in lattice QCD.

Asymptotic freedom, which means that in very high-energy reactions, quarks and gluons interact very weakly creating a quark–gluon plasma.

The present model of the universe starts with enormous energies, and as it expands the individual constituents cool down first into a stage where all forces are unified with all particles zero mass into a quark-gluon plasma

As cooling continues bound hadrons appear.

The quark gluon plasma is studied experimentally at the LHC experiments.

So all the models of particle physics are utilized for the Big Bang model of the universe, and the creation of bound quarks is developed within an extended standard model.

If you read the article you will see that a lot of the model is still at the research stage experimentally.