So in short is a belief in rebirth a necessity for Buddhist practice?
After going through all the responses above I was very much satisfied with what Jayantha has said. I would like to add something to this discussion - I think rebirth is part of Buddhist doctrine. But the real question is rebirth of what? and rebirth of whom?
According to the Buddha, there are four elements of Existence which go to compose the body. They are (1) Prithvi; (2) Apa; (3) Tej; and (4) Vayu. Question is, when the human body dies, what happens to these four elements? Do they also die along with dead body? According to The Buddha they join the mass of similar elements floating in (Akash) space. When the four elements from this floating mass join together, a new birth takes place. This is what the Buddha meant by rebirth, as I have understood it. It must be noted that the body dies. But the elements are ever-living. This is the kind of rebirth in which the Buddha believed. Great light is thrown upon the subject by Sariputta in his dialogue with Maha-Kotthita. The Buddha was not an absolute annihilationist. He was an annihilationist so far as soul was concerned. He was not an annihilationist so far as matter was concerned. (I think Andrei Volkov is also saying the same point when he is talking about "complete annihilation).
There is another concern here. It is about rebirth of Whom? Does the same dead person take a new birth? Did the Buddha believe in this thesis? The answer is, "Most improbable." The answer depends upon the elements of existence of the dead man meeting together and forming a new body; then the possibility of the rebirth of the same sentient being is possible. If a new body is formed after a mixture or the different elements of the different men who are dead, then there is rebirth but not the rebirth of the same sentient being. This point has been well explained by sister Khema to King Pasenadi. Where she ends up saying 'The Tathagata exists after death...exists not after death', does not apply." (Again we can match Jayantha's write up regarding Kalama Sutta.) I have drawn lot from Buddha and His Dhamma Book 4, Part 2, section 1, sub section 2. Hoping for further discussion.