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

Here's one more pointer. Ladner's theorem states that if $P \neq NP$ then there is a problem in $NP-P$ which is not $NP$-complete.

Richard E. Ladner: On the Structure of Polynomial Time Reducibility. J. ACM 22(1): 155-171 (1975)

Unfortunately the known proofs of this result produce a fairly unnatural problem. The zombie-metaphorical explanation is you take the head and torso of an $NP$-complete set and surgically stick on arms and legs of a polynomial time computable set. (If that ain't unnatural, I don't know what is.)

See this writeup for two proofs.

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$?")

There are much stronger versions of the P vs. NP conjecture that complexity theorists often take as axioms, and that imply that many problems are not NP-complete. The most standard class of assumptions is the conjecture that the NP hierarchy does not collapse. You can define NP as the analysis of polynomially bounded solitaire games with complete information. For instance, generalized Sudoku is such a game and it is known to be NP-complete. The nth level of the polynomial hierachy $\Sigma^n P$ and $\Pi^n P$ can be similarly defined by games with $n$ half moves. For instance, suppose that in generalized Sudoku, there is an initial board, and I can first try to make you lose by filling in some of the squares, with restrictions. (Like say only the "red" squares, and only with certain numbers.) After that you can move. Then whether I can win is a natural problem in $\Sigma^2 P$.

In particular, the assertion that the polynomial hierarchy PH does not collapse implies that NP does not equal co-NP. If a problem is both in NP and co-NP, it cannot be NP-complete without collapse. (Proof: If solitaire were equivalent to co-solitaire, than a game with two half moves would also be equivalent to solitaire.) A good near example is the graph isomorphism problem, which is in NP and co-AM. AM is like NP but with randomness; it is the model in which Arthur gets an adaptive proof in response to a randomized question and becomes statistically convinced. AM is not quite NP, but it is conjectured to be the same. So if you put two standard conjectures together, graph isomorphism is not NP-complete either. Edit: Ryan and Harrison both point out that Boppana, Håstad, and Zachos proved that if NP is contained in co-AM, then PH is contained in $\Sigma^2 P$. I.e., the hierarchy would collapse at the second level whether or not AM = NP. In particular this applies to graph isomorphism.

Problems in BQP, such as factoring, are strongly suspected not to be NP-complete either, but it is an open problem to show that that would imply that the polynomial hierarchy collapses. However, decision-based problems from factoring, such as whether a number is square-free, are known to be in both NP and co-NP. This was known earlier, but it follows particularly quickly from the fact that primality is in P, since that certifies a factorization. Addendum: Certification of factorization is equivalent to certification of primality, which as David pointed was first proved by Vaughan Pratt.