Usage of Zero-knowledge proofs for NP-complete languages It is well known that if OWFs/PRGs exist, then there is a zero knowledge proof for any NP-complete language, say G3C (graph coloring in 3 colors). The zero-knowledge notion maintains that any malicious verifier that interacts with the prover can be simulated by a PPT algorithm (including the communication) and thus, doesn't gain any advantage from the prover's replies. 

Yet, if a PPT algorithm can find a coloring in a graph with non-negligible probability (even without interacting with a prover), then the whole notion of zero-knowledge proofs for NP-Complete languages becomes useless!

Is there a distribution over graphs that enables generating graphs for which no PPT algorithm can find a 3-coloring in non-negligible probability?? (under the assumptions of P!=NP and OWF &amp; PRGs exist). Or a distribution over graphs that enables generating graphs for which no PPT algorithm can determine if they are in G3C or not with non-negligible advantage? 
 Otherwise I can't see how such a ZK proof can be beneficial.
If one-way functions exist, then there is a distribution over graphs (or SAT formulas, or ...) having the property you're asking for.  In short, just put the OWF through the Cook-Levin reduction.

In a little more detail, Cook-Levin transforms the NP witness-finding question "what is a preimage of $y = f(x)$?" (for random unknown $x$) into the NP witness-finding question "what is a 3-coloring of this graph $G$?", by converting $y$ into a graph $G$ such that any 3-coloring of $G$ can be efficiently converted back to a preimage of $y$ under $f$.