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][1], 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][2].


  [1]: http://ac.els-cdn.com/0095895679900844/1-s2.0-0095895679900844-main.pdf?_tid=95292268-d97f-11e3-8ebc-00000aab0f27&acdnat=1399862953_65c045be84565e62b46167f0e2a6eb1e
  [2]: http://www-personal.umich.edu/~jblasiak/ujhandout.pdf