computational complexity - What techniques exist to show that a problem is not NP-complete?

There are several results along these lines known, all of which use one technique: You show that if the problem is NP-complete, then some very strongly believed complexity hypothesis fails. In the following explanations, an asterisk* means "unless an extremely strongly-believed complexity hypothesis (e.g., P $neq$ NP) fails".

Factoring is known to be not NP-complete.* One has to be slightly careful with Factoring for a technical reason: in its most natural version ("Given a number, factor it") it is not a "decision problem". A standard decision problem version is: "Given n, L, and U, is there a prime factor of n between L and U?" This is easily seen to be in NP -- a witness is just a factor of n between L and U. On the other hand, this problem is not* NP-complete because it is also in coNP: there is a witness that proves n has no prime factor between L and U, namely a prime factorization of n. So if Factoring were NP-complete then all problems in NP would be in coNP; i.e., NP=coNP. So the asterisk in this paragraph refers to the assumption NP $neq$ coNP, which is extremely strongly believed.

The Graph-Isomorphism problem is a more interesting example. Telling if two given graphs are isomorphic is obviously in NP (the witness is the isomorphism). But in addition, Graph-Nonisomorphism is "almost" in NP as well. Specifically, it is in the class AM, which is essentially "randomized NP". There is a constant-round randomized "interactive proof" that two graphs are not isomorphic. (Basically, if you put the two graphs behind your back, randomly relabel them, then show them to a prover and the prover can always tell you which is which, then you become convinced the graphs must be non-isomorphic.) From this it follows that Graph-Isomorphism is not NP-complete.* Because if it were, Graph-Nonisomorphism would be coNP-complete, and then all coNP problems would be in AM. And this is known to imply that "the polynomial time hierarchy collapses" (the Boppana-Hastad-Zachos Theorem), which is very widely believed not to happen.

(By the way, I assumed you were mostly interested in problems that aren't NP-complete because they are (presumably) too easy. In the other direction, there are also problems that shouldn't be NP-complete because they are too hard; e.g., $Sigma_2$-complete problems like, "Given a Disjunctive Normal Form formula $phi$ and a number $s$, is there an equivalent DNF formula of size at most $s$?")