For purposes of Brevity, I will refrain explanations on Gemara and Tosfot.
Your question presuppose that, out of the havdala in Tefilat Haamida, there is a possibility to make Havdala without wine, as for instance, following some Geonim and Rishonim opinion, the blessings of Brit Mila on Yom Kippur or 9 beav are said without wine cup, or the Shehecheyanu of Yom Kippur is without wine.
See accurately the words of the Rambam Zmanim, Shabbat, Chapter 29.
The mitsva of Havdala itself is a mitsva MideOrayta following the Rambam opinion:
א מִצְוַת עֲשֵׂה מִן הַתּוֹרָה לְקַדֵּשׁ [א] אֶת יוֹם הַשַּׁבָּת בִּדְבָרִים שֶׁנֶּאֱמַר (שמות כ-ח) 'זָכוֹר אֶת יוֹם הַשַּׁבָּת לְקַדְּשׁוֹ'. כְּלוֹמַר זָכְרֵהוּ זְכִירַת שֶׁבַח וְקִדּוּשׁ. וְצָרִיךְ לְזָכְרֵהוּ בִּכְנִיסָתוֹ וּבִיצִיאָתוֹ. בִּכְנִיסָתוֹ בְּקִדּוּשׁ הַיּוֹם וּבִיצִיאָתוֹ בְּהַבְדָּלָה:
short and loose translation: To remember the Shabbat, by words, at its starting time (Kiddush) and its ending time (Havdala).
ו __ מִדִּבְרֵי __סוֹפְרִים [ז] לְקַדֵּשׁ עַל הַיַּיִן וּלְהַבְדִּיל עַל הַיַּיִן. וְאַף עַל פִּי שֶׁהִבְדִּיל בַּתְּפִלָּה צָרִיךְ לְהַבְדִּיל עַל הַכּוֹס.
Rabbinically we need to make Kiddush on wine and Havdala on wine. And even though he already made Havdala in prayer (Ata Chonantanu in Amida), he needs to make Havdala on a cup.
So, there is a Scriptural Mitsva of Kiddush and Havdala, which can be accomplished without wine. And Rabbinically, we need to make it with a cup of wine. And even if the mitsva was already made without wine, e.g. Havdala in Tefila, the rabbinical requirement to make it on wine is not fulfilled , to do this we need a second Havdala.
From the words of the Rambam, we can infer that the unique reason to make Havdala after the Havdala of the Tefila is the cup of wine. Thus, if someone already made Havdala in Tefila, he needs to make a second Havdala only with a cup of wine, so Poskim discussed if Tinok or Motsae 9 beAv, and for reasons of right education of children ("lemisrach"), the choice is to make Havdala after 9 beAv.
But the a question remains not solved: If someone forgot to say Havdala in Tefila. See Tur Siman 294 said something in name of Rabenu Yona, and further we will learn something about this last question:
וכתב הרבינו יונה אף אם אין לו כוס בלילה וסבר שיהיה לו למחר (כוס יין) אין צריך לחזור ולהתפלל אלא אם כן סבור שאף למחר לא יהיה לו ולפי זה אף בתשעה באב שחל באחד בשבת אם טעה ולא הבדיל בתפילה אין צריך לחזור ולהתפלל כיון שמבדיל על הכוס במוצאי תשעה באב.
Rabbenu Yona wrote that if someone failed to say Havdala in Tefila and has no wine at home, if he believes to get wine tomorrow, no need to pray a second time for the Havdala part of the Tefila. ___And accordingly to this, if, when 9 Beav starts motsae Shabbat, one did forget Havdala in tefila of Maariv, there is no need to pray Maariv again, because of the intent to do Havdala after 9 beav.
You see that the importance of the wine in the Havdala is enough for wait the time of havdala. In other words, The Takana is DAVKA to make havdala on wine, not as brachot of Brit mila. without wine there is havdala in Tefila only.
next step. A Nazir with Havdala.
Following some Rishonim, even Nazir itself need to drink wine Kiddush and Havdala, but we rule as Rabenu Tam and the Rambam above that wine for K&H is derabanan. May be that Nazir need to find a Chamar Medina.
It seems that everyone who knows that he will not find wine and does not hearing from another need to pray Amida a second time with Havdala.