What were the previous births of the characters of Mahabharata?
This chapter of the Adi Parva of the Mahabharata describes exactly who incarnated as each of the major characters in the Mahabharata. It's too long a chapter to quote the whole thing here, so let me just address some important people.
I discuss the previous births of Draupadi and the Pandavas here. As you said, Bhishma was an incarnation of one of the Vasus, a group of eight Vedic gods controlling various aspects of nature, but more specifically he was the Vasu known as Dyaus Pita, AKA Prabhasa, god of the sky. And as you said Shishupala was an incarnation of Vishnu's gatekeeper Jaya, who had previously been born Hiranyakashipu and Ravana, while Shishupala's brother Dantavakra was an incarnation of Vijaya, who had previously been born as Hiranyaksha and Kumbhakarn, as I discuss in this answer.
Now Bhishma's father Shantanu was a rebirth of Mahabhisha, a king of the Ikshvaku dynasty. After Mahabhisha died, he went to Devaloka, where on one occasion he stared at the goddess Ganga when her robe slipped by accident. As a result, he was cursed by Brahma to be born on earth and to be tormented by Ganga, as described in this chapter of the Adi Parva of the Mahbharata:
One day the celestials had assembled together and were worshipping Brahman. Many royal sages and king Mahabhisha also were present on the spot. And Ganga, the queen of rivers, also came there to pay her adorations to the Grandsire. And her garments white as the beams of the moon was displaced by the action of the wind. And as her person became exposed, the celestials bent down their heads. But the royal sage Mahabhisha rudely stared at the queen of rivers. And Mahabhisha was for this cursed by Brahman, who said, 'Wretch, as thou hast forgotten thyself at the sight of Ganga, thou shalt be re-born on earth. But thou shall again and again attain to these regions. And she, too, shall be born in the world of men and shall do thee injuries. But when thy wrath shall be provoked, thou shalt then be freed from my curse.'
Shantanu's second wife Satyavati, who was the daughter of the king Uparichara Vasu but raised by fishermen, was the next birth of Acchoda, mind-born daughter of the Pitris or ghosts of departed ancestors. (I discuss another mind-born daughter of the Pitris in this question.) Acchoda was caught admiring Uparichara Vasu, so the Pitris gave her the following curse, as described in this chapter of the Harivamsa:
You have just now seen an air-voyager, isn't it... he is called uparichara-vasu... when he takes birth in human world, then you will become his daughter... while remaining a virgin you will deliver the son of sage parAshara, which son of yours, namely veda-vyAsa, will ramify veda canons... still remaining a virgin you will return to your own abode, that which is unachievable otherwise... Later you will auspiciously give rise to two sons of mahAbhiSha, namely king shantanu; one boy will be the glorious vichitraviirya, while the other will be the righteous chitrA~Ngada; and later, on your begetting them you will return to your abode; thus you have to undergo this wretched life on earth because you sidestepped from the morals of manes... will become the daughter of that king vasu through lady adrika, whom you have just now seen along with uparichara-vasu on aircraft... all this happens in twenty-eight dwApara era... then you will emerge as the daughter of a fish, namely from this lady adrika who by then transfigures as a fish
Satyavati's son Krishna Dwaipayana Veda Vyasa (or Vyasa for short) was an incarnation of Vishnu, but he was also the next birth of the sage Aparantamas, an earlier compiler of the Vedas described in this chapter of the Shanti Parva of the Mahabharata.
Vyasa's son Pandu was apparently the incarnation of the god of Purity, while Vidura was the incarnation of Yama god of death, as described in this chapter of the Adi Parva of the Mahbharata:
[Dhritarashtra's] younger brother who was possessed of great strength and was really a great being known as Pandu, devoted to truth and virtue, was Purity's self. And, O king, thou shouldst know that he who was known on earth as Vidura, who was the first of all virtuous men ... was the god of Justice himself.
There's no information in that chapter as to Dhritarashtra's previous birth, but as far as the Kauravas go, Duryodhana was the incarnation of Kali (the demon of the Kali Yuga) and his brothers were incarnations of Rakshasas:
The evil-minded and wicked king Duryodhana, the destroyer of the fair fame of the Kurus, was born of a portion of Kali on earth. He it was who caused all creatures to be slain and the earth to be wasted; and he it was who fanned the flame of hostility that ultimately consumed all. They who had been the sons of Pulastya (the Rakshasas) were born on earth among men of Duryodhana's brothers, that century of wicked individuals commencing with Duhasasana as their first.
Arjuna's son Abhimanyu was an incarnation of Varchas, son of Chandra the moon god, and the reason he died so early is that Chandra didn't want him to be gone too long:
And he who was known as the mighty Varchas, the son of Soma, became Abhimanyu of wonderful deeds, the son of Arjuna. And before his incarnation, O king, the god Soma had said these words to the celestials, 'I cannot give (part with) my son. He is dearer to me than life itself. Let this be the compact and let it be not transgressed. The destruction of the Asuras on earth is the work of the celestials, and, therefore, it is our work as well. Let this Varchas, therefore, go thither, but let him not stay there long.'
The Upapandavas were incarnations of the Vishwadevas, Dristadyumna was an incarnation of Agni, Amba/Sikhandi was the incarnation of a demon, and the Upapandavas are incarnations of the Vishwadevas:
Know also, O monarch, that the mighty car-warrior Dhrishtadyumna was a portion of Agni. And know also that Sikhandin, who was at first a female, was (the incarnation of) a Rakshasa. And, O bull in Bharata's race, they who became the five sons of Draupadi, those bulls amongst the Bharata princes, were the celestials known as the Viswas. Their names were Pritivindhya, Sutasoma, Srutakirti, Satanika, Nakula, and Srutasena, endued with mighty energy.
Kripacharya was an incarnation of the Rudras, Shakuni was an incarnation of Dwapara (embodiment of the Dwapara Yuga), and Satyaki and Drupada were incarnations of the Maruts:
And, O king, that Brahman sage who, on earth, was known by the name of Kripa and was the embodiment of all manliness was born of the tribe of the Rudras. And the mighty chariot-fighter and king who on earth was known by the name of Sakuni, that crusher of foes, thou shouldst know, O king, was Dwapara himself (the third yuga). And he who was Satyaki of sure aim, that upholder of the pride of Vrishni race, that oppressor of foes, begotten of the portion of gods called the Maruts. And that royal sage Drupada who on earth was a monarch, the first among all persons bearing arms, was also born of the same tribe of the celestials.
Ashwatthama was an incarnation of Shiva; see the Shiva Purana. And Shalya was an incarnation of Prahlada's brother Sanhlada:
He who had been known as Samhlada, the younger brother of Prahlada, became among men the famous Salya, that bull amongst Valhikas.
Being a Vaishnava, I'd like to end with one last individual:
And he, called Vasudeva [Krishna], endued with great valour, was among men a portion of him called Narayana--the god of gods--eternal.
Note: “The question: What were the previous births of the characters of Mahabharata?” is licensed by Stack Exchange Inc (https://hinduism.stackexchange.com/); user contributions licensed under CC BY-SA.