Are there examples of statements that have been proven whose consistency proofs came before their proofs?

One of the main applications of Shelah's pcf theory is the celebrated theorem that if $\aleph_\omega$ is a strong limit, then $2^{\aleph_\omega}\lt\aleph_{\omega_4}$.

The conclusion of the theorem, however, is an immediate consequence of the generalized continuum hypothesis, and so the consistency of this statement was known long before Shelah made his proof. The surprising aspect of the theorem is precisely the fact that it is provable without any assumption on the continuum function.

There are likely many other examples of statements that were first proved from a GCH assumption (or which are trivial under GCH), but for which later this assumption was removed. And indeed, in these cases the later more general arguments are also often more difficult, as you suggest.

Here are my favorite examples of statements whose consistency was established and cherished before their proof.

1. The Keisler-Shelah isomorphism theorem stating that two elementarily equivalent structures have isomorphic ultrapowers (proved using in $ZFC+GCH$ by Keisler in 1964, and in $ZFC$ by Shelah in 1971).

2. Several algebraic results (normal forms, divison algorithms, etc) concerning the "left-distributive algebras of one generator" were first established by Richard Laver by assuming (very) large cardinals (known as (I3) in the literature). Later Patrick Dehornoy eliminated the large cardinal assumption in these results by giving a representation in the braid group.

By the way, a left distributive algebra is a set with one binary operation * satisfying the left distributive law $a*(b*c)=(a*b)*(a*c)$; the operation of conjugation in a group is an example. Here is an old paper of Laver about this topic; there is by now a large literature on the subject.

3. In some cases, the consistency proof of a statement $S$ can be combined with some absoluteness argument to yield a proof of $S$ (this was hinted at in the second example cited by Steprans). There are all sorts of absoluteness theorems in logic; the standard tool of the trade is the Shoenfield absoluteness theorem that shows that all sorts of consistency results can be translated into $ZFC$-proofs.

A very good example, I believe, is A. Blass' theorem that AC holds if and only if every vector space has a basis.

It was well established that the existence of a vector space without a basis is consistent with the negation of AC, by Lauchli, 1963. Only 21 years later it was proved that ZF+not AC proves such a vector space exists.

There are probably some other similar examples of equivalent assertions of AC of similar nature.