I'm not one hundred percent clear if this is what you mean, and even if it is I don't see an obvious way to make it actually work, but it might be of interest anyway.

The [Rado graph][1] is "the infinite random graph," and it's known to contain induced copies of every finite graph. (Actually I think that characterizes it -- certainly having countably many vertices and containing induced copies of every countable graph does.) So if you pick a large random graph, with probability 1 it'll contain an induced copy of every small enough graph. Unfortunately "large enough" means "exponential in the size of the random graph," so this isn't actually useful.

I don't know if you can do better than exponential for specific classes of graphs (and I sort of doubt it for any class that's interesting), although if you take a subgraph rather than an induced subgraph it might be easier. There's a famous conjecture of Erdos that says that Ramsey numbers of bounded-degree graphs are linear, but that's considerably stronger than what's needed...

ETA: After giving it some more thought, an n-vertex graph with bounded *average* degree is a subgraph of a random graph with, say, cn (for some large c depending on the average degree) vertices w/h/p. So in particular, planar graphs are subgraphs of slightly larger random graphs, and 3-colorability is known to be NP-complete even for planar graphs. But I suspect that the important thing is induced subgraphs, which (again) seems much trickier. 

  [1]: http://en.wikipedia.org/wiki/Rado_graph