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 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.