The Gemara Berachos 27b talks about making havdalah before the end of Shaabos:
רַבִּי יֹאשִׁיָּה מְצַלֵּי שֶׁל מוֹצָאֵי שַׁבָּת בְּשַׁבָּת: אוֹמֵר הַבְדָּלָה עַל הַכּוֹס אוֹ אֵינוֹ אוֹמֵר הַבְדָּלָה עַל הַכּוֹס? תָּא שְׁמַע דְּאָמַר רַב יְהוּדָה אָמַר שְׁמוּאֵל: מִתְפַּלֵּל אָדָם שֶׁל מוֹצָאֵי שַׁבָּת בְּשַׁבָּת וְאוֹמֵר הַבְדָּלָה עַל הַכּוֹס.
A similar dilemma was raised concerning the fact that Rabbi Yoshiya would pray the evening prayer of the conclusion of Shabbat on Shabbat: After praying, while it is still Shabbat, does he recite havdala over the cup of wine or does one not recite havdala over the cup of wine? Come and hear a resolution to this, as Rav Yehuda said that Shmuel said: One prays the evening prayer of the conclusion of Shabbat on Shabbat and recites havdala over the cup of wine.
As emphasized by the codifiers, this is only is extenuating circumstances. What is the halacha is one accidently said havdalah before the proper time? Does he need to say havdalah again?
Also, the Shulchan Aruch (O.C. 293:3) says that one does not make the beracha on the candle when making havdalah early. Is that only when making havdalah very early, or could one make the beracha on a (previously lit) candle after sunset but still before the time for ending Shabbos, thus saving one who accidentally said havdalah early from having to repeat that beracha?