A very interesting example: consider semi-simplicial sets (alias $\Delta$-sets).
These are simplicial sets without degeneracies, and there is an ``adjoin degeneracies'' functor from semi-simplicial sets to simplicial sets that is left adjoint to the evident forget degeneracies functor. One can compose this with geometric realization or one can define geometric realization of semi-simplicial sets directly. Define a weak equivalence of semi-simplicial sets to be a map whose geometric realization is a homotopy equivalence (weak equivalence is the same since these are CW complexes). Since it is a presheaf category, the category of semi-simplicial sets is bicomplete, and I've described the obvious weak equivalences, which satisfy the two-out-of-three property. Matthew Thibault convinced me that this truly natural category with weak equivalences does not admit a model structure for any choice of cofibrations or fibrations.

EDIT: Dylan, if you believe the comments already posted, you know the proof.
According to Tom, the acyclic fibrations have to be the isomorphisms. But
then all maps are cofibrations, since they are the maps with the LLP wrt the
acyclic fibrations. If you believe Karol that it cannot be the case that all
monomorphisms are cofibrations, or just that $\ast$ cannot be cofibrant, you already
have a contradiction to such a model structure.

classesof counterexamples see ncatlab.org/nlab/show/category+with+weak+equivalences . For instance non-model categories with weak equivalences go by names such as "relative category", "category of fibrant objects", "cofibration category", "Waldhause category" etc. $\endgroup$ – Urs Schreiber Jun 8 '13 at 13:10