What makes a distribution GNU and are there Linux distributions, that are not GNU?
The Free Software Foundation argues that the majority of Linux distributions are in fact GNU systems, which happen to use a Linux kernel. They base this claim on the fact that GNU was a longstanding project to develop a free operating system before Linux came along, and that the kernel was only the last missing piece. They are right in that practically all Linux-based desktop and server distributions use at least some GNU components, perhaps most importantly the GNU C Library (glibc), GNU Core Utilities (coreutils) and the Bash shell. Furthermore, Linux kernel development is inherently tied to GCC, due to the utilization of GCC extensions.
Some embedded system, perhaps most notably Google's Android, don't use any GNU components or libraries. In Android, for instance, the GNU C Library is replaced by Google's own, BSD-based Bionic C Library. The FSF agrees that it is not appropriate the refer to such system as "GNU systems" or "GNU/Linux", but on the other hand they wouldn't want these to be referred to as merely "Linux" systems either. At least we can draw the conclusion that there seems to be consensus about the fact that using GNU tools to build the kernel, does not make a system a "GNU system".
The history of the GNU/Linux terminology goes back to the early 1990s.
In 1991 Linus Torvalds began the Linux kernel project out of his bedroom in Helsinki. Not long afterwards the Linux kernel began to gain substantial traction, aided by the rise of the Internet.
Richard Stallman's GNU project was at the time still planning to use the HURD microkernel as the kernel of the planned GNU operating system. However, when Linux distributions (free Unix-like operating systems based on the Linux kernel) started forming around the new Linux kernel project, Stallman became interested. When the Debian project began in 1993, under the leadership of Ian Murdock, the FSF gave some financial support to the young project. However, the Debian developers quickly parted ways with Stallman and the FSF, in part on technical issues. One issue for example was that Stallman wanted to retain debugging symbols in the program, while Debian wanted to strip them.
Once Debian and the FSF parted ways, Stallman requested that Debian refer to itself as GNU/Linux. The request was made to Bruce Perens, since Murdock had handed leadership over to him. Since these organizations had parted on good terms, and shared (and share) common goals, the Debian developers did as he asked. Of course it is true that Stallman has promoted such names independently, but the cooperation of an actual Linux-based operating system in referring to themselves as such has been significant in promoting the usage of such a name.
The rationale as given by Stallman included that (a) the core of the system aside from the Linux kernel was largely GNU tools, (b) the Linux kernel was in some sense the culmination/completion of the GNU project, who had been trying to get a working kernel for some time, so it should use this name as a way of acknowledging and reminding people of the ideals of the GNU project. Reason (a) tends to be mentioned rather more often, though it was not exactly true then, and is even less true now, Though clearly important parts of a Linux based operating system depend on GNU tools e.g. bash, gcc, binutils, gdb, libc etc., in some cases these can be replaced by other tools. So, such arguments are at least debatable, and have, indeed, been much debated.
As far as I know only Debian and (some of) its derivatives (following the lead of its parent) refer to themselves as GNU/Linux. However, the other so-called Linux distributions such as Fedora, Gentoo, etc. are in substance no different from Debian - it is mostly the same software. So one has equally good reason to refer to them as GNU/Linux.
There aren't a lot of systems around using the Linux kernel without the GNU userland, since the two to a large extent developed together and are intertwined in various ways. (For example the Linux kernel is written in the extended (GNU) C of gcc, and won't build with a standard C compiler.) As Thomas said, the obvious example is Android, but since it has been so heavily forked by Google it is questionable whether it is correct to refer to the Android kernel as Linux anymore, though there is talk of a merge/reconciliation in the future.
On a side note, it is unfortunate to note that Stallman and the FSF apparently push the GNU/Linux terminology rather hard. For example, Jonathan Corbet wrote in an LWN comment that the FSF refuses to talk to him unless he uses the term GNU/Linux. Jon, in addition to being a LWN founder, is also a senior and respected kernel developer. In its entirety, the comment says:
Just to be clear on this: we stopped asking the FSF for comments many years ago because the FSF refused to talk to us without prior promises from us on what we would say and which terms we would use. We are unwilling to make such promises. If the FSF's policy on such things has changed, we would be pleased to know about it.
This is clearly a reference to the insistence on GNU/Linux terminology among other things.
The above history is covered in some detail in Chapter 6 ("Boot Then Root") of "Rebel Code" by Glyn Moody.
An operating system is a combination of a kernel and a userland. Basically, the kernel manages the hardware while the userland provides a comprehensive interface to the users.
In a common GNU/Linux distribution, Linux provides the kernel while the GNU project brings the userland tools. GNU was started way before Linux, and provides with a large amount of utilities to build a full operating system.
However, they were missing a kernel. Although they had the Hurd kernel, it was taking too long to be ready. And then came Linux with the help of a big enthusiasm around it, it has evolved faster than the Hurd.
You now have a userland and a kernel from two different projects. And as each is essential to have an operating system, why not name the association GNU/Linux so each project is given its share of the credit?
You have other userlands like the BSD utils or BusyBox. However they are more or less complete compared to the GNU utilities and some software will work only with a GNU userland. For example, most of the BSD operating systems are using GCC as a compiler while LLVM will soon change this situation.
And as an universal operating system, you can run Debian with a FreeBSD kernel and a GNU userland.