I've got two fakedexes going and each one takes different approaches with the fossils.
First one breaks convention by having a two more elemental Pokémon. First one is a Rock/Electric styracosaurus that stores electricity in its neck-based horns, then fires it out of its main horn, while the second is an offensive Rock/Ice stegosaurus with ice crystals running down its back. There's also a single stage Rock/Dragon spinosaurus.
The second fakedex is specifically themed to be based around a desert and fossils and such, so not only are there more fossils, the starters themselves are fossil Pokémon. Grass starter is a Rock/Grass archaeopteryx/bird combination that has two forms in the final stage - if it reaches the evolutionary level normally, it drops the Rock type and gains a new secondary type. If it knows Ancient Power when it hits the evolution level (learnable at a move relearner), then it keeps Rock/Grass. Fire starter has the same gimmick and is a Rock/Fire and Fire/Steel ankylosaurus, and Water starter does the same being a Rock/Water and Water/Dark tyrannosaurus.
Lastly, the regular fossils of that region come in two pair of two stage Pokémon in addition to another single stage one. The first pair are a Rock/Dark sabertooth tiger and a Rock/Bug giant scorpion, and the second pair are a Rock/Flying pteranodon and a Rock/Water plesiosaurus, with the last fossil being a single stage Rock/Ground ampelosaurus based on a mountain range.
Dunno about abilities or Megas yet, but I'm working on it.