A. Havdala over bread:
If there is no wine or Chamar Medina beverages available it does not suffice to say Havdala over bread as is allowed by Kiddush.  Rather one is to delay saying Havdala until he receives wine or other Chamer Median as will be explained next.
B. Eating prior to Havdala when no beverages are available for Havdala:
Wine will be available late Saturday night:  If wine or other valid beverages will become available before Sunday morning, according to all it is forbidden to eat or drink until one says Havdala over wine.
Wine will be available on Sunday: If he expects to receive wine or other valid beverages on Sunday during the day, one is to fast until he receives the wine and says Havdala. If one is weak and it is difficult for him to fast until that point, he may be lenient to eat and drink prior to Havdala. [One may however drink water prior to saying Havdala even if he is not weak. Although based on our custom to avoid drinking even water before Havdala seemingly one is to withhold himself from even drinking water if he is able to do so.]
- Ruling of Admur in Kuntrus Achron: In Kuntrus Achron 296/1 Admur leans to learn that after midday of Sunday one may begin eating if he has still not received wine for Havdala. [Accordingly some learn that if on Motzei Shabbos one knows he will not receive wine or other valid beverages until after midday of Sunday, one may begin eating immediately on Motzei Shabbos, as is the rule in the next case.]
Wine will not be available until after Sunday:  In the event that wine or other significant beverages are not available to say Havdala, then if he is unable to receive wine until Sunday night, he is allowed to eat and drink immediately on Motzei Shabbos if he said Havdala in Davening. If he did not say Havdala in Davening he must repeat Shemoneh Esrei prior to drinking.
C. The blessing of Besamim and Meoreiy Haeish:
In the event that one does not have any Halachically valid beverages available for Havdala he is to nevertheless to say on Motzei Shabbos the blessing over fire as soon as he sees it and the blessing of Besamim if he has spices.
 As Kiddush has a connection to the bread being that Kiddush may only be done in place of a meal. However Havdala is independent of eating a meal and hence has no connection to bread to allow saying Havdala over it. [Ibid]
 A dispute in this matter is brought in Admur. Some rule [Geonim; 1st opinion in Michaber] since one is allowed to say Kiddush over the bread, and Havdala is secondary to Kiddush on this night, he may likewise say Havdala over the bread. Others [Rosh; 2nd opinion of Michaber] however rule in such a situation it is better to say Kiddush over Chamer Medina than to say it over bread. Practically the custom in these countries is like the former opinion. [ibid] So is the ruling of Rama in our current wording of the Shulchan Aruch, however some prints have written the Rama rules like the latter opinion. [See Kaf Hachaim 296/28]
Other opinions: Michaber, based on Klalei Haposkim rules like the latter opinion. [Kaf Hachaim 296/27]
 Some Poskim [1st opinion in Michaber 296/3] rule if no wine will be available until Sunday morning, from the letter of the law it is permitted to immediately eat and drink if he said Havdala during Davening. It is however an act of piety to fast until he receives wine on Sunday. Others [2nd opinion in Michaber] however rule that if one will receive wine on Sunday it is forbidden from the letter of the law for him to eat or drink until he says Havdala over wine. Practically the Halacha is as stated above that we are stringent unless one is very weak and unable to fast in which case he may be lenient in a Rabbinical matter.[ibid]
So rules also Elya Raba like the latter opinion, and so seems to be the ruling of Michaber based Klalei Haposkim. [Kaf Hachaim 296/30]
 299/1; See Ketzos Hashulchan 93 footnote 8. Vetzaruch Iyun why this ability to drink water was completely omitted by Admur.
 Ketzos Hashulchan 94 footnote 10; and so also plainly rules Piskeiy Teshuvos 296/12
 294/2 and 296/12
 Even if one expects to receive wine on Monday he is not obligated to fast until then and rather he is allowed to eat immediately if he said Havdala in Davening. [294/2; 296/12]
Other Opinions: Some [Mahram brought in M”A] rule in such a case one is to say the blessing of Havdala without a cup. Practically we do not rule this way. [Kaf Hachaim 296/29]