Quantum chemical molecular dynamics (QM/MD) simulations of ensembles of C(2) molecules on the Ni(111) terrace show that, in the absence of a hexagonal template or step edge, Haeckelite is preferentially nucleated over graphene as a metastable intermediate. The nucleation process is dominated by the swift transition of long carbon chains toward a fully connected sp(2) carbon network. Starting from a pentagon as nucleus, pentagons and heptagons condense during ring collapse reactions, which results in zero overall curvature. To the contrary, in the presence of a coronene-like C(24) template, hexagonal ring formation is clearly promoted, in agreement with recent suggestions from experiments. In the absence of step edges or molecular templates, graphene nucleation follows Ostwald's "rule of stages" cascade of metastable states, from linear carbon chains, via Haeckelite islands that finally anneal to graphene.