I have always been impressed by the following construction of graphs with arbitrarily large chromatic number and girth. The construction I will mention is due to Nesetril-Rodl, and the the first such construction is due to Laszlo Lovasz.

The construction is based on hypergraphs, and indeed the only known constructions build recursively using hypergraphs. Call a hypergraph a $[p,k,n]$-hypergraph if it is a $k$ uniform with no $p$-cycles and chromatic number at least $n$. Suppose for a fixed $p$ and $n$ you can produce a $[p,K,n]$-hypergraph for all values of $K$.

The inductive step is to use this to show a $[p+1,k,n]$-hypergraph exists, but in doing so it requires that a $[p,K,n]$-hypergraph for several values of $K$ which are (much) larger than $k$. To start the induction, one needs a $[1,k,n]$- hypergraph which is given by the $k$ uniform graph with $(k-1)(n-1) + 1$ vertices.

The construction can also be found in section 2.3 here.