As @Kaveh stated, this question is only interesting if we assume $P \neq NP$; the rest of my answer takes this as an assumption, and mostly provides links to further wet your appetite. Under that assumption, by Ladner's theorem we know that there are problems that are neither in $P$ nor $NPC$; these problems are called $NP$-intermediate or $NPI$. Interestingly enough, Ladner's theorem can be generalized to many other complexity classes to produce similar intermediate problems. Further, the theorem also implies, that there is an infinite hierarchy of intermediate problems that are not poly-time reducible to each other in $NPI$.
Unfortunately, even with the assumption $P \neq NP$ it is very difficult to find natural problems that would be provably $NPI$ (of course you have the artificial problems coming from the proof of Ladner's theorem). Thus, even assuming $P \neq NP$ at this time we can only believe some problems to be $NPI$ but not prove it. We come to such beliefs when we have reasonable evidence to believe that an $NP$ problem is not in $NPC$ and/or not in $P$; or just when it has been studied for a long time and avoided fitting into either class. There is a pretty comprehensive list of such problems in this answer. It includes such all-time favorites as factoring, discrete log, and graph-isomorphism.
Interestingly, some of these problems (notable: factoring and discrete log) have polynomial time solutions on quantum computers (i.e. they are in $BQP$). Some other problems (such as graph-isomorphism) are not known to be in $BQP$, and there is ongoing research to resolve the question. On the other hand, it is suspected that $NPC \not\subseteq BQP$, thus people don't believe we will have an efficient quantum algorithm for SAT (although we can get a quadratic speed up); it is an interesting question to worry about what sort of structure $NPI$ problems need in order to be in $BQP$.