To answer the question, the discussion really centers around Pesach Sheini. What exactly does a Jew who is tamei b'zman Pesach to do? Well, since he can't makriv, the only thing he would do is everything else - maror, matza and maggid (he would do everything as though it was Pesach without a korban Pesach and Chagiga). On Pesach Sheini, he would offer the korban Pesach, eat it and do marror and maggid again. He would not eat chometz for the duration of Pesach Sheini, and possibly seven days afterwards.
Maggid is d'oraisa. Just because the Mishnah outlines what Maggid is supposed to include doesn't mean it didn't exist before hand. Also, we see that Pesach and Matza are not taloi - meaning on Pesach night you have a mitzvah d'oraissa to eat Matza regardless of your tamei status.
There would be a requirement of 4 cups and haseiba. The Haggadah as we have it is a conglomeration of various parts that were stiched together and became a standard text. However, suffice to say, there would certainly be elements to keep children entertained. If the exact choice of phrase of Mah Nishtana wasn't necessarily part of Maggid, certainly to ask questions would be, specifically by the child, and specifically the four questions in the Torah (the four sons). There would certainly be narrative of our initial history - we were once idolators, or we were once slaves in Egypt, there would be discussion about the source of that slavery - Bris Bein HaBesarim. Afterwhich - why we were saved from almost total annihilation. Perhaps a recital of the passages in Parshas Bo - the night of the leaving - so the korban Pesach etc. a mention of the 10 plagues and their culmination at the Yam Suf.
There would certainly be Hallel, if not the Song at the Sea.
If you were to ask me, I would say the Haggadah is more an outline than anything else. It presents an overview of how we were miraculously taken out with a strong arm and mighty hand by Hashem, together with subtle hints at how we can escape our own exile. The Medrashim abound as to what happened.
The premise of the questioner assumes that since it was de'rabbonon it must have been a decree mandated at some stage in history. In that case, it follows that before that point it wasn't mandated and hence didn't exist. This is not true. We have a Mesorah on how to perform the Pesach seder. I don't imagine that the generation that entered into Eretz Yisrael didn't have 4 cups of wine. It is certainly feasible to imagine that all the elements and aspects of the Seder they had, as much as we did, perhaps the Nusach would be slightly different, but I can't really imagine why it would be - perhaps the discussion in Bnei Brak would not be included, but rather the conclusion - that tonight is different in that we recount the Exodus that happened this night, and that the Torah says: kol yamei chayeha is a reference to Olam Hazeh and Olam Haba not just days and nights - i.e. why are we recounting the Exodus on this night.
The Haggadah itself recounts how the sages stayed up the whole night recounting the Exodus as something praiseworthy. Certainly the generation that witnessed the miracles or at least had a first-hand account of the miracles would spend the whole night up listening to the recounting of the Exodus. It would have been the central point in their lives. Like Holocaust survivors and their children, it would have been on their lips exactly what happened and how Hashem saved them. Yehoshua ben Nun would have recounted perhaps mostly what happened, just as the Haggadah describes. So while the Haggadah we have today is a stitched together book intended to provide an outline and structure to Maggid, it doesn't negate that what they did before Chazal was very different in terms of Maggid.
I will say this though. In the times of the Beis Hamikdash there would be no shulchan orech of eggs and soup and fish and chicken!
There may have been a necessity to cut out the beginning of Haggadah - the discussion in Bnei Brak (which is not so essential), so that there would be enough time to eat the Chagigah and Korban Pesach before Chatzos, after which the discussion would continue - hallel, bentching and the last cup of wine. There would be no time for anything else, and of course no Afikomen.