There is a whole slew of examples given by the $J$-semi model structures which arise in the study of operads and algebras over an operad. A $J$-semi model category satisfies most of the axioms of a model category, but two have to be tweaked. First, not all trivial cofibrations lift against fibrations; only those with cofibrant domain do. The lifting of cofibrations against trivial fibrations works as usual. Second, not all maps factor into a trivial cofibration followed by a fibration; only those maps with cofibrant domain do. The other factorization works fine.
These come up because without strong hypotheses on the underlying category $M$, one doesn't know that $Op(M)$ is a model category ($M$ needs to have a monoidal fibrant replacement functor and a commutative Hopf interval object, see e.g. the nLab) . But with very minimal hypotheses on $M$ (symmetric monoidal and cofibrantly generated suffice) you do get a $J$-semi model category. The concept of a $J$-semi model category--under a different name--appeared first in a preprint of Hovey called Monoidal Model Categories (Theorem 2.3), available from his website. This paper was a follow-up to the famous paper Algebras and Modules in Monoidal Model Categories, by Schwede and Shipley. Hovey was trying to figure out what could be said in the absence of the monoid axiom from that paper.
The best reference for $J$-semi model categories is Markus Spitzweck's Operads, Algebras and Modules in General Model Categories. This defines them more generally than Hovey and develops a theory which mimics that in Hovey's book on Model Categories. Corollary 8 of Spitzweck shows that Tyler's example is a $J$-semi model category which is not a model category. It proves in particular that if $M$ is a cofibrantly generated left proper model category with domains of the generating cofibrations cofibrant and cofibrant unit, then commutative monoids in $M$ form a $J$-semi model category. This paper also shows that if $O$ is an operad which is cofibrant in the projective model structure on collections, then algebras over $O$ and modules over a cofibrant $O$-algebra $A$ have $J$-semi model structures. Getting actual model structures rather than $J$-semi model structures requires more hypotheses on the underlying category $M$, and is part of my current thesis work.
Another example in the same style as $J$-semi model categories, but on the fibrant side, are the semimodel categories which appear in Clark Barwick's "On the Dreaded Right Bousfield Localization." A right semimodel category satisfies all the usual axioms, but factorizations into cofibrations followed by trivial fibrations and the lifting criterion for trivial fibrations only hold if the codomain is fibrant. A left semimodel category is a $J$-semi model category. Barwick proves that the right Bousfield localization of $M$ is a right semimodel categories, even if $M$ is not right proper. This gives many examples of right semimodel categories which are not model categories.
Here are a few other examples I've found of things which are not model categories.
In this paper of Schwede he mentions on page 22 that the category of commutative DFSPs is not a model category. A DFSP is a degreewise functor with smash product. They are models for brave new rings in $\Gamma$-spaces. The failure is because the $E_\infty$ structure on the cofibrant replacement $QS^0$ is not equivalent to a commutative simplicial monoid structure. Again, this example demonstrates the difference between $J$-semi model structures and model structures.
In this paper of Mandell he mentions on page 38 that this category $\mathcal{E}_{F_q}$ is not a model category, even though it has a homotopy category. It's the category of $E_\infty$ $F_q$ algebras. The failure is related to Tyler's example, but is different because the operad is cofibrant in this case.
In these notes of Bergner she mentions on page 16 that the category $SSet^{\Delta^{op}}_{disc}$ of Segal precategories does not have a model structure with cofibrations being monomorphisms and weak equivalences levelwise. She gives an example where factorization fails. This kind of failure of a model structure is also mentioned in recent work of Shipley and Hess. Again the issue is related to needing cofibrations to be monomorphisms.
Here are some examples of model categories which are not cofibrantly generated (since the last paragraph of the OP's question suggests these would also be of interest)
Hovey and Christiensen's paper "Quillen model structures for relative homological algebra" studies model structures on the category of unbounded chain complexes of $R$-modules and characterizes which are cofibrantly generated (including examples which are not).
Boris Chorny's "An example of a non-cofibrantly generated model category" gets such a model structure on diagrams in Top.
Adámek, Herrlich, Rosicky, and Tholen's "Weak Factorization Systems and Topological Functors" gets a model structure on the category of small categories which is not cofibrantly generated. It's the one coming from the weak factorization system (Full functors, Topological functors).
Isaksen's "A model structure on the category of pro-simplicial sets" is another non-cofibrantly generated model category.
Lack's "A 2-categories companion" proves that $Cat^{\mathcal{A}}$ for $\mathcal{A}=2$ is not cofibrantly generated.
This post of Emily Riehl's suggests that the injective model structure on diagrams might not be cofibrantly generated. I thought about how to find an example where I could prove it failed, but couldn't. I plan to ask my own MO question about this soon.
EDIT: The last example is cofibrantly generated, both on $Ch(R)$ (see Theorem 2.3.13 in Hovey's book) and on diagram categories $M^D$. Riehl was asking about $Ch(A)$ for an abelian category $A$ with enough injectives. There's potentially an example in that setting of a model category which is not cofibrantly generated, but it doesn't seem to be known. As for diagram categories, in order to know the injective model structure on $M^D$ exists you usually need to know $M$ is combinatorial (and $D$ is small, of course). In HTT, Lurie proves (A.2.8.2) that if $M$ is combinatorial then $M^D$ is combinatorial, so it's cofibrantly generated. Furthermore, $id:M^D_{inj} \stackrel{\to}{\gets} M^D_{proj}:id$ is a Quillen equivalence. I learned this from the nLab, but the proof is trivial once you know the statement because the maps in question are all defined levelwise, so it's just the fact that $id_M$ is a Quillen equivalence.
EDIT #2: In Chapter 4 of May and Sigurdsson's Parameterized Homotopy Theory another type of "almost model category" comes up. In particular, given a topological model category $C$ you can try to define an $h$-type model structure analogous to what is done for spaces. So a map is an $h$-fibration if it has CHP (i.e. the RLP with respect to $X\to Cyl(X)$ for all $X$), and is an $h$-cofibration if it has HEP (i.e. the LLP with respect to $Cocyl(X)\to X$ for all $X$). Say that $f$ is a strong $h$-fibration if it has the relative CHP, and a strong $h$-cofibration if it has the relative HEP. Then using $h$-fibrations and strong $h$-cofibrations OR using $h$-cofibrations and strong $h$-fibrations give two new structures which satisfy all the axioms for a model category except that the factorization axiom becomes
"Any map $f: X \to Y$ factors as $X \to Mf \to Y$ where the first map is a strong $h$-cofibration and the second has a section which is an $h$-acyclic strong $h$-cofibration, and $f$ factors as $X\to Nf \to Y$ where the first map is a strong $h$-fibration and the second has a section which is an $h$-acyclic strong $h$-fibration."
This is Theorem 4.3.1. Theorem 4.4.2 gives a hypothesis under which this almost model structure becomes a model structure. You need to know that given a chain of $h$-acyclic $h$-cofibrations $j_n:Z_n\to Z_{n+1}$ and given a compatible system $q_n:Z_n\to Y$ which gives $q:$colim $Z_n \to Y$ then colim $Nq_n \to Nq$ is an isomorphism in $C$. So the failure of these structures on $C$ to form a model structure has to do with the failure of this axiom, which I imagine is a bit surprising to those who don't work with model categories a lot.