The Buddha taught rebirth because it is something real that is related to the arising of suffering; namely, the re-arising of the delusion of "self" as a result of the emotions created by kamma (actions). Whenever the idea of "I" or "mine" arises as a result of an action, this is "rebirth".

Discerning an absence of rebirth in the mind is necessary to understand emptiness. Also, rebirth (kamma & results) is one example of causality.

A Buddhist doctrine that make sense without rebirth is the Three Characteristics. Seeing the Three Characteristics is unrelated to rebirth.

Knowing Nirvana is also unrelated to rebirth although, similar to Emptiness, knowing Nirvana coincides with knowing an absence of rebirth in the mind.

As for a rebirth as an "afterlife", this is an unknowable unproveable primitive superstition. Any claims there is a "Truth of Afterlife Rebirth" is obviously a lie or falsehood because there is no evidence for this belief. It is only a "belief" but not a "truth".

I've decided to create a second answer for this question, that's completely different to the first one.

Please also see this answer.

TL;DR

Denying rebirth-of-self view while clinging to self view is wrong view, because this is annihilationism and brings the unenlightened to hedonism.

Denying rebirth-of-self view after discarding self view is the noble right view. Rebirth without self view is simply the continuation of suffering and the continuation of the chain of conditioned processes. It's not about the rebirth of a specific person or being or self or consciousness.

Rebirth view can be used as skillful means (upaya) to remove the habit of misconduct, cultivate virtue and generate the path to liberation. Rebirth view is the middle way and is the right view with effluents/ taints.

Long answer

Denying rebirth-of-self, while clinging to self-view, appears to be wrong view. This is unskillful means because it directs the mind of the unenlightened towards hedonism and nihilism. This is also the view of annihilationism.

And what is wrong view? 'There is nothing given, nothing offered, nothing sacrificed. There is no fruit or result of good or bad actions. There is no this world, no next world, no mother, no father, no spontaneously reborn beings; no contemplatives or brahmans who, faring rightly & practicing rightly, proclaim this world & the next after having directly known & realized it for themselves.' This is wrong view.
MN 117

Holding on to the rebirth-of-self, while clinging to the fetter of self view, is a right view with effluents/ taints.

"And what is the right view with effluents, siding with merit, resulting in acquisitions? 'There is what is given, what is offered, what is sacrificed. There are fruits & results of good & bad actions. There is this world & the next world. There is mother & father. There are spontaneously reborn beings; there are contemplatives & brahmans who, faring rightly & practicing rightly, proclaim this world & the next after having directly known & realized it for themselves.' This is the right view with effluents, siding with merit, resulting in acquisitions.
MN 117

Why is this the case? This is because siding with merit, one could use this as skillful means (upaya), a helpful tool, to remove the habit of misconduct, cultivate virtue and generate the path to liberation.

The Buddha is the doctor (Iti 100) who treats the illness which is suffering (dukkha). This is a medicine that he has prescribed.

“And for the sake of what benefit should a woman or a man, a householder or one gone forth, often reflect thus: ‘I am the owner of my kamma, the heir of my kamma; I have kamma as my origin, kamma as my relative, kamma as my resort; I will be the heir of whatever kamma, good or bad, that I do’? People engage in misconduct by body, speech, and mind. But when one often reflects upon this theme, such misconduct is either completely abandoned or diminished. It is for the sake of this benefit that a woman or a man, a householder or one gone forth, should often reflect thus: ‘I am the owner of my kamma, the heir of my kamma; I have kamma as my origin, kamma as my relative, kamma as my resort; I will be the heir of whatever kamma, good or bad, that I do.’ .....

“This noble disciple reflects thus: ‘I am not the only one who is the owner of one’s kamma, the heir of one’s kamma; who has kamma as one’s origin, kamma as one’s relative, kamma as one’s resort; who will be the heir of whatever kamma, good or bad, that one does. All beings that come and go, that pass away and undergo rebirth, are owners of their kamma, heirs of their kamma; all have kamma as their origin, kamma as their relative, kamma as their resort; all will be heirs of whatever kamma, good or bad, that they do.’ As he often reflects on this theme, the path is generated. He pursues this path, develops it, and cultivates it. As he does so, the fetters are entirely abandoned and the underlying tendencies are uprooted.
AN 5.57

Once self-view is discarded, rebirth-of-self view will also be discarded. This is the noble Right View.

"And what is the right view that is noble, without effluents, transcendent, a factor of the path? The discernment, the faculty of discernment, the strength of discernment, analysis of qualities as a factor for awakening, the path factor of right view in one developing the noble path whose mind is noble, whose mind is without effluents, who is fully possessed of the noble path. This is the right view that is noble, without effluents, transcendent, a factor of the path.
MN 117

How do we know that rebirth-of-self view will be discarded? This is the higher teaching for those who have understood anatta, as taught in MN 38 and SN 22.85.

Rebirth without self view is simply the continuation of suffering and the continuation of the chain of conditioned processes. It's not about the rebirth of a specific person or being or self or consciousness.

“Yes, friend,” he replied, and he went to the Blessed One, and after paying homage to him, sat down at one side. The Blessed One then asked him: “Sāti, is it true that the following pernicious view has arisen in you: ‘As I understand the Dhamma taught by the Blessed One, it is this same consciousness that runs and wanders through the round of rebirths, not another’?”

“Exactly so, venerable sir. As I understand the Dhamma taught by the Blessed One, it is this same consciousness that runs and wanders through the round of rebirths, not another.”

“What is that consciousness, Sāti?”

“Venerable sir, it is that which speaks and feels and experiences here and there the result of good and bad actions.”

“Misguided man, to whom have you ever known me to teach the Dhamma in that way? Misguided man, have I not stated in many ways consciousness to be dependently arisen, since without a condition there is no origination of consciousness? But you, misguided man, have misrepresented us by your wrong grasp and injured yourself and stored up much demerit; for this will lead to your harm and suffering for a long time.”
MN 38

“But, friend, when the Tathagata is not apprehended by you as real and actual here in this very life, is it fitting for you to declare: ‘As I understand the Dhamma taught by the Blessed One, a bhikkhu whose taints are destroyed is annihilated and perishes with the breakup of the body and does not exist after death’?”

“Formerly, friend Sāriputta, when I was ignorant, I did hold that pernicious view, but now that I have heard this Dhamma teaching of the Venerable Sāriputta I have abandoned that pernicious view and have made the breakthrough to the Dhamma.”

“If, friend Yamaka, they were to ask you: ‘Friend Yamaka, when a bhikkhu is an arahant, one whose taints are destroyed, what happens to him with the breakup of the body, after death?’—being asked thus, what would you answer?”

“If they were to ask me this, friend, I would answer thus: ‘Friends, form is impermanent; what is impermanent is suffering; what is suffering has ceased and passed away. Feeling … Perception … Volitional formations … Consciousness is impermanent; what is impermanent is suffering; what is suffering has ceased and passed away.’ Being asked thus, friend, I would answer in such a way.”
SN 22.85

Why now do you assume 'a being'?
Mara, have you grasped a view?
This is a heap of sheer constructions:
Here no being is found.

Just as, with an assemblage of parts,
The word 'chariot' is used,
So, when the aggregates are present,
There's the convention 'a being.'

It's only suffering that comes to be,
Suffering that stands and falls away.
Nothing but suffering comes to be,
Nothing but suffering ceases.
SN 5.10

"Then, Bāhiya, you should train yourself thus: In reference to the seen, there will be only the seen. In reference to the heard, only the heard. In reference to the sensed, only the sensed. In reference to the cognized, only the cognized. That is how you should train yourself. When for you there will be only the seen in reference to the seen, only the heard in reference to the heard, only the sensed in reference to the sensed, only the cognized in reference to the cognized, then, Bāhiya, there is no you in connection with that. When there is no you in connection with that, there is no you there. When there is no you there, you are neither here nor yonder nor between the two. This, just this, is the end of stress (suffering)."
Ud 1.10

I think this is excellent because it finally tells us what rebirth really is in Buddhism. It's not falsehood. It's not truth. It's just skillful means (upaya), a helpful tool. A middle way between falsehood and truth.

First Noble Truth: saṃkhittena pañc·upādāna·k·khandhā dukkhā - In short, the five aggregates of clinging is suffering.

If all mental activities cease at death, there will be no craving after death as it is clearly a mental activity. If that's the case, apart from craving, the second noble truth should include things like breathing, eating, drinking, checking for vehicles before crossing the road and pretty much anything else that keeps you alive.

The third noble truth(s) would be both Nibbana and death.

Apart from the noble eightfold path that one needs to practice with years of dedication, the fourth noble truth(s) would include hanging yourself, shooting yourself, drowning, starving to death, death by lethal injection, sleeping on a railway, jumping from a skyscraper or pretty much doing whatever you like until you end up dead.

Imagine a criminal with such a belief saying "I became a serial killer so the government would make me enlightened by capital punishment."

Such a religion would mainly provide laughter to people instead of being taken seriously. :)

Why buddha teach rebirth?

Because highest goal of buddhism is to avoid rebirth.

In reality even buddha teach or doesn’t, Rebirth mechanism is still there.

And it’s the origin of every suffer.

Rebirth Concept was there in India[Early stages India called Dambadiwa] among Rishi's who meditated and achieved "Dyana" supreme mental states. Actually, Buddha taught us how to stop rebirth. This is the concept Lord Buddha understood from his Omniscience. Though the rebirth concept was there even "Rishi" did not have Supreme mundane wisdom to explain rebirth concept exactly. They might have seen previous births in some extend where lord buddha seen rebirth to the eternity. That is why his wisdom called Omniscience.

Why do we wanted to avoid pain of Cancer? Because it causes whole life suffering. By knowing that we are taking precautionary measures to avoid cancer. If we found it earlier stages we completely remove it from the body. Furthermore, to avoid occuring cancer cells we do chemotherapy.

Similarly, Lord Buddha understood from his Omniscience that the creatures are sufferings from eternal journey of samsara within this 31 levels of the universe [4 Hells, 26 Divines and Earth]. Out of these 31 most of the creatures travelling through 4 hells only. Very similar to the cancer.

Giving this example he said. If someone takes a certain amount of soil from the earth on the nail tip of the thumb finger, that much creatures will go to the divine worlds , the Brahma worlds and the human world,. Rest of the creatures equal to the earth's soil will go to hell. That is why Lord Buddha introduce the hells as creature's great house.

By knowing this great disaster with "Metta and Karuna" he wanted to stop creatures facing this agony while rescuing them.

Without convincing the reality of this samsara journey, the painful sorrowful agony one can face and going through, if he talk about the luxury life then no one wanted to attain Nibbana. People love this lust life.

Lord Buddha in his Omniscience understood the way to overcome this dependent origination circle by stopping the rebirth. That is where he introduce us four noble truth and the eightfold path.

Now your question was answered. Without knowing the cause or the reason we cannot overcome the issue. We need to stop occurrence to stop the result occurring due to that cause.

That is why causality was explained.

May Triple Gem Blessed You.

I do not think the Buddha taught that it was necessary to assume rebirth. Take this from the Kalama Sutta:

"'Suppose there is a hereafter and there is a fruit, result, of deeds done well or ill. Then it is possible that at the dissolution of the body after death, I shall arise in the heavenly world, which is possessed of the state of bliss.' This is the first solace found by him.

"'Suppose there is no hereafter and there is no fruit, no result, of deeds done well or ill. Yet in this world, here and now, free from hatred, free from malice, safe and sound, and happy, I keep myself.' This is the second solace found by him.

Clearly, any of the meditative practices the Buddha taught focus attention on the rebirth that happens in this moment, here and now.

Was rebirth introduced in the First or Second Turnings, and why did the Buddha teach it?

I think the idea of rebirth preceded (predated, already existed earlier than) the Buddha's doctrine:

Early Hinduism, Jainism and Buddhism

The idea of reincarnation has early roots in the Vedic period (c. 1500 – c. 500 BCE), predating the Buddha and the Mahavira.

I think that, therefore, the question[s] which the Buddhist doctrine had to answer included, "Is the 'rebirth' doctrine true, to what extent is it true (how does it fit with other Buddhist doctrines), what does it mean exactly, how does it work, what is kamma?" and similar questions.

Would any of the Buddhist doctrines, excluding karma and rebirth, fail to make sense without rebirth?

I don't know, maybe some of these might be affected:

• Stages of enlightenment -- that perhaps you won't be enlightened in this life, but even so that's not too late (and that effort is always even though immediate result may seem impossible)
• An incentive (albeit "siding with merit and resulting in acquisition") for morality: including, both, generosity and harmlessness
• The concept of merit may affect the relationship between lay society and the sangha

• The three characteristics:

  • anatta e.g. as explained in this answer -- if rebirth doesn't exist, does that mean that we live and die, and if so isn't that identifying with the aggregates?
  • anicca -- so you're saying that death is permanent, not impermanent?
  • dukkha -- without the doctrine of rebirth, some people may develop strange or wrong ideas around killing or suicide as being an escape from dukkha ... also the doctrine that "craving to live (or, for becoming)" and "craving to die (or, for cessation)" are, both, forms of craving

• The superiority (super-humanity) of the Buddha (not according to the suttas, necessarily, but e.g. the Jataka tales and the Mahāvaṃsa)

• Combining cyclic cosmology with the dhamma's being timeless (previous and future Buddhas)
• Atheism -- no sense in worshipping the Gods too much, they too are subject to rebirth
• Hope or optimism -- no matter how bad things seem now, etc.
• Some sense in which dhamma is called timeless (akalika)

The concept of rebirth is an axiomatic corolary of 'Karma'.

Also if rebirth does not exist then nibbana i.e. 'blowing out' doesn't make sense.

For e.g. without rebirth and without afterlife in heaven or hell you will be essentially 'blown out' nibbanafied without doing anything.

So nibbana makes sense only because rebirth exist, because in rebirth the flame continues.

Also, murdering sentient beings (in a painless way) would also be equivalent to liberating them from suffering if rebirth does not exist.

So it is a pretty central doctrine, even if you don't emphasize on Karma.

OP: Was rebirth introduced in the First or Second Turnings?

Rebirth has been around since the Earth first started turning on its axis. And perhaps much.. much.. longer than that.

The Buddha stated in the Assu Sutta:

"This is the greater: the tears you have shed while transmigrating & wandering this long, long time — crying & weeping from being joined with what is displeasing, being separated from what is pleasing — not the water in the four great oceans.

"Long have you (repeatedly) experienced the death of a mother. The tears you have shed over the death of a mother while transmigrating & wandering this long, long time — crying & weeping from being joined with what is displeasing, being separated from what is pleasing — are greater than the water in the four great oceans.

"Long have you (repeatedly) experienced the death of a father... the death of a brother... the death of a sister... the death of a son... the death of a daughter... loss with regard to relatives... loss with regard to wealth... loss with regard to disease. The tears you have shed over loss with regard to disease while transmigrating & wandering this long, long time — crying & weeping from being joined with what is displeasing, being separated from what is pleasing — are greater than the water in the four great oceans.

"Why is that? From an inconstruable beginning comes transmigration. A beginning point is not evident, though beings hindered by ignorance and fettered by craving are transmigrating & wandering on. Long have you thus experienced stress, experienced pain, experienced loss, swelling the cemeteries — enough to become disenchanted with all fabricated things, enough to become dispassionate, enough to be released."

Based on the sutta above, I made a calculation in this answer that every person has been reborn at least 20 quintillion (20 x 10¹⁸) times. But I'm guessing that it's a lot longer than that.

OP: why did the Buddha teach it? E.g. was it necessary to understand emptiness, causality, etc.?

The Buddha taught it because this was what he realized to be true, and this knowledge is also useful to understand two things. The first is that suffering has happened since forever. The second is that it is not possible to escape suffering through death. Only ending craving and the ten fetters would result in freedom from suffering.

According to the Dvedhavitakka Sutta:

"When the mind was thus concentrated, purified, bright, unblemished, rid of defilement, pliant, malleable, steady, & attained to imperturbability, I directed it to the knowledge of recollecting my past lives. I recollected my manifold past lives, i.e., one birth, two... five, ten... fifty, a hundred, a thousand, a hundred thousand, many eons of cosmic contraction, many eons of cosmic expansion, many eons of cosmic contraction & expansion: 'There I had such a name, belonged to such a clan, had such an appearance. Such was my food, such my experience of pleasure & pain, such the end of my life. Passing away from that state, I re-arose there. There too I had such a name, belonged to such a clan, had such an appearance. Such was my food, such my experience of pleasure & pain, such the end of my life. Passing away from that state, I re-arose here.' Thus I remembered my manifold past lives in their modes & details.

"This was the first knowledge I attained in the first watch of the night. Ignorance was destroyed; knowledge arose; darkness was destroyed; light arose — as happens in one who is heedful, ardent, & resolute.

"When the mind was thus concentrated, purified, bright, unblemished, rid of defilement, pliant, malleable, steady, & attained to imperturbability, I directed it to the knowledge of the passing away & reappearance of beings. I saw — by means of the divine eye, purified & surpassing the human — beings passing away & re-appearing, and I discerned how they are inferior & superior, beautiful & ugly, fortunate & unfortunate in accordance with their kamma: 'These beings — who were endowed with bad conduct of body, speech & mind, who reviled the Noble Ones, held wrong views and undertook actions under the influence of wrong views — with the break-up of the body, after death, have re-appeared in the plane of deprivation, the bad destination, the lower realms, in hell. But these beings — who were endowed with good conduct of body, speech, & mind, who did not revile the Noble Ones, who held right views and undertook actions under the influence of right views — with the break-up of the body, after death, have re-appeared in the good destinations, in the heavenly world.' Thus — by means of the divine eye, purified & surpassing the human — I saw beings passing away & re-appearing, and I discerned how they are inferior & superior, beautiful & ugly, fortunate & unfortunate in accordance with their kamma.

Since the Buddha made speaking the truth a very important precept, it is obvious that he couldn't be lying when he said that he saw with his divine eye, the truth of rebirth, where, with the break-up of the body, after death, beings reappear in other destinations. The phrase "break-up of the body" shows that it is not a metaphorical death.

OP: Would any of the Buddhist doctrines, excluding karma and rebirth, fail to make sense without rebirth?

If it is possible to escape suffering through death, the Buddha would have taught suicide. Basically, the Noble Eightfold Path becomes redundant without rebirth.

Rebirth is actually not the important point. The important point is that it is not possible to become free from suffering through death.

The Truth of Rebirth seems to be one of the larger points of dispute between participants on this site. See here and here for similar questions and answers. I guess this is not all that surprising to me since the site seems heavily represented by Western practitioners. In my experience it seems that westerners have (and I definitely include myself here) a particularly difficult time with the Truth of Rebirth as taught by the Buddha. Here is what Venerable Thanissaro Bhikkhu has to say about this:

Yet as these Buddhist religions have come to the West, they have run into a barrier from modern Western culture: Of all the Buddha's teachings, rebirth has been one of the hardest for modern Westerners to accept. Part of this resistance comes from the fact that none of the dominant world-views of Western culture, religious or materialistic, contain anything corresponding to the idea of repeated rebirth. Plato taught it, but — aside from an esoteric fringe — few in the modern West have treated this side of his teaching as anything more than a myth.

For people who have felt burned or repelled by the faith demands of Western religion, there is the added barrier that the teaching on rebirth is something that — for the unawakened — has to be taken on faith. They would prefer a Buddhism that makes no faith demands, focusing its attention solely on the benefits it can bring in this life.

There seem to be many approaches on this site:

1. Simply denying outright that the Buddha taught rebirth.
2. The Buddha taught the reality of rebirth as a (re)birth that takes place in this very life whenever self-views of "I" and "mine" occur. No "afterlife" concept of rebirth was taught or acknowledged by the Buddha.
3. Admitting he taught it, but insisting it was just skillful means.
4. Rebirth as a combination of metaphor and upaya.
5. Those who take rebirth at face value, but insist that mere experience can end.
6. Like above, but do not posit an end to this mere experience.
7. Those who think rebirth (generally) can be known incontrovertibly through reason alone.
8. Those who think rebirth requires a dose of faith to be known (generally).

And probably a number of other views that I've missed. Myself, I'm with 6 and 7.

Was rebirth introduced in the First or Second Turnings, and why did the Buddha teach it?

To my mind, unquestionably it was taught and introduced. I think the Buddha taught it because it was/is a conventional truth and the Buddha taught the truth.

Would any of the Buddhist doctrines, excluding karma and rebirth, fail to make sense without rebirth?

Yes, I think there are obvious logical problems and inconsistencies that present if you deny the truth of rebirth. For instance, as BodhiWalker mentions above one could seek the end of suffering by merely ending this current life. Even more problematic, one could "liberate" others from suffering by murdering sentient beings painlessly. That's monstrous and I want nothing to do with it. I want to make quite clear, I'm sure this is not what others have in mind when denying or glossing the truth of rebirth. I'm emphatically not concluding that those who deny or gloss the truth of rebirth are murderous monsters, just that denying or glossing the truth of rebirth presents logical problems that I don't see a way around.

Anyway, I think Venerable Thanissaro Bhikkhu's article above is excellent and highly recommend reading it many times and contemplating these questions.