How could humans have interbred with Neanderthals if we're a different species?
Short answer
The concept of species is poorly defined and is often misleading. The concepts of lineage and clade / monophyletic group are much more helpful. IMO, the only usefulness of this poorly defined concept that is the &quot;species&quot; is to have a common vocabulary for naming lineages.
Note that Homo neanderthalis is sometimes (although it is rare) called H. sapiens neanderthalis though highlighting that some would consider neanderthals and modern humans as being part of the same species.
Long answer
Are neanderthals and modern humans really considered different species?
Often, yes they are considered as different species, neanderthals being called Homo neanderthalis and modern humans are being called Homo sapiens. However, some authors prefer to call neanderthals Homo sapiens neanderthalis and modern humans Homo sapiens sapiens, putting both lineages in the same species (but different subspecies).
How common were interbreeding between H. sapiens and H. neanderthalis
Please, have a look at @iayork's answer.
The rest of the post is here to highlight that whether you consider H. sapiens and H. neanderthalis to be the same species or not is mainly a matter of personal preference given that the concept of species is mainly arbitrary.
Short history of the concept of species
To my knowledge, the concept of species has first been used in the antiquity. At this time, most people viewed species as fixed entities, unable to change through time and without within-population variance (see Aristotle and Plato's thoughts). For some reason, we stuck to this concept even though it sometimes appears to not be very useful.
Charles Darwin already understood that as he says in On the Origin of Species (see here)

Certainly no clear line of demarcation has as yet been drawn between species and sub-species- that is, the forms which in the opinion of some naturalists come very near to, but do not quite arrive at the rank of species; or, again, between sub-species and well-marked varieties, or between lesser varieties and individual differences. These differences blend into each other in an insensible series; and a series impresses the mind with the idea of an actual passage.

You might also want to have a look at the post Why are there species instead of a continuum of various animals?
Several definitions of species
There are several definitions of species that yield me once again to argue that we should rather forget about this concept and just use the term lineage and use an accurate description of the reproductive barriers or genetic/functional divergence between lineage rather than using this made-up word that is &quot;species&quot;.
I will below discuss the most commonly used definition (the one you cite) that is called the Biological species concept.
Problems with the definition you cite

A species is often defined as the largest group of organisms where two hybrids are capable of reproducing fertile offspring, typically using sexual reproduction.

Only applies to species that reproduce sexually
Of course, this definition only applies to lineages that use sexual reproduction. If we were to use this definition for asexual lineages, then every single individual would be its own species.
In practice
In general, everybody refers to this definition when talking about sexual lineages but IMO few people are correctly applying for practical reasons of communicating effectively.
How low the fitness of the hybrids need to be?
One has to arbitrarily define a limit of the minimal fitness (or maximal outbreeding depression) to get an accurate definition. Such boundary can be defined in absolute terms or in relative terms (relative to the fitness of the &quot;parent lineages&quot;). If, the hybrid has a fitness that is 100 times lower than any of the two parent lineages, then would you consider the two parent lineages to belong to the same species?
Type of reproductive isolation
We generally categorize the types of reproductive isolation into post-zygotic and pre-zygotic reproductive isolation (see wiki). There is a lot to say on this subject but let's just focus on two interesting hypothetical cases:

Let's consider two lineages of birds. One lineage has blue feathers while the other has red feathers. They absolutely never interbreed because the blue birds don't like the red and the red birds don't like the blue. But if you artificially fuse their gametes, then you get a viable and fertile offspring. Are they of the same species?

Let's imagine we have two lineages of mosquitoes living in the same geographic region. One flying between 6 pm and 8 pm while the other is flying between 1 am and 3 am. They never see each other. But if they were to meet while flying they would mate together and have viable and fertile offsprings. Are they of the same species?


Under what condition is the hybrids survival and fertility measured
Modern biology can do great stuff! Does it count if the hybrid can't develop in the mother's uterus (let's assume we are talking about mammals) but can develop in some other environment and then become a healthy adult?
Ring species in space
As you said in your question, ring species is another good example as to why the concept of species is not very helpful (see the post Transitivity of Species Definitions). Ensatina eschscholtzii (a salamander; see DeVitt et al. 2011 and other articles from the same group) is a classic example of ring species.
Species transition through time
Many modern lineages cannot interbreed with their ancestors. So, then people might be asking, when exactly did the species change occurred? What generation of parent where part of species A and offspring where part of species B. Of course, there is no such clearly defined time in which transition occurred. It is more a smooth transition from being clearly reproductively isolated (if they were placed to each other) from being clearly the same species.
Practical issue - Renaming lineages
How boring it would be if every time we discover the two species can in some circumstances interbreed, we had to rename them! That would be a mess.
Time
Of course, when we talk about a species we refer to a group of individuals at a given time. However, we don't want to rename the group of individuals of interest every time a single individual die and get born. This notion yield to the question of how long in time can a single species exist. Consider a lineage that has not split for 60,000 years. Was the population 60,000 years ago the same species as the one today? The two groups may differ a lot phenotypically and may actually be reproductively isolated if they were to exist at the same time.
Special cases
When considering a few special cases, the concept of species become even harder to apply.
The Amazon molly (a fish) is a &quot;species&quot; that have &quot;sexual intercourse&quot; without having &quot;sexual reproduction&quot; and there are no males in the species! How is it possible? The females have to seek for sperm in a sister species in order to activate the development of the eggs but the genes of the father from the sister species are not used (Kokko et al. (2008)).
In an ant &quot;species&quot;, males and females can both reproduce by parthenogenesis (some kind of cloning but with meiosis and cross-over) and don't need each other to reproduce. In this respect, males could actually be called females. But they still meet to reproduce together. The offsprings of a male and a female (via sexual reproduction) are sterile workers. So males and females are just like two sister species that reproduce sexually to create a sterile army to protect and feed them (Fournier et al. (2005)).
Bias
It often brings fame to discover a large new species. In consequence, scientists might tend to apply a definition of species that allow them to tell that their species is a new one. A typical example of such eventual bias concern dinosaurs where many new fossils are abusively called a new species while they sometimes are just the same species but at a different stage of development (according to this TED).
So why do we still use the concept of species?
Naming
IMO, its only usefulness is that it allows us to name lineages. And it is very important that we have the appropriate vocabulary to name different lineages even if this brings us to make a few mistakes and use some bad definitions.
The alternative use of the concept of lineage
It is important though that we are aware that the concept of species is poorly defined and that if we need to be accurate that we can talk in terms of lineages. The main issue with the term lineage is not semantic and comes about the fact that gene lineages may well differ considerably from what one would consider being the &quot;species lineage&quot; as defined by the &quot;lineages of most sequences&quot;... but this is a story for another time.
In consequence
In consequence to the above issues, we often call two lineages that can interbreed to some extent by different species names. On the other hand, two lineages that can hardly interbreed are sometimes called by the same species name but I would expect this case to be rarer (as discussed by @DarrelHoffman and @AMR in the comments).
Homo lineages
I hope it makes sense from the above that the question is really not related to the special case of the interbreeding between the Homo sapiens and the Homo neanderthalis lineages. The issue is a matter of the definition of species.
Video and podcast
SciShow made a video on the subject: What Makes a Species a Species?
For the French speakers, you will find an interesting (one hour long) podcast on the consequence of the false belief that the concept of species is an objective concept on conservation science at podcast.unil.ch &gt; La biodiversité - plus qu'une simple question de conservation &gt; Pierre-Henry Gouyon

Here is a related answer