See this article by REabbi Yigal Gross of Michlelet Hertzog. Here is a summary of the Halacha Lemasseh:
Per Shulchan Aruch and Rama 296:2
אין מבדילין על הפת אבל על השכר מבדילין אם הוא חמר מדינה וה"ה לשאר משקין חוץ מן המים: הגה וטוב יותר להבדיל על כוס פגום של יין מעל שכר (אבודרהם) ונהגו להבדיל במוצאי פסח על שכר ולא על יין משום דחביב עליו
Havdalah may not be recited over bread. However, he may recite Havdalah over any beverage that is the “wine of the region,”with the exception of water. RAMA: It is better to say Havdalah over a blemished cup of wine rather than liquor (Avudraham)
There is a disagreement how far to take the S"A's ruling "חוץ מן המים".
- Rabbi Sternbuch (Teshuvot Vehanhagot - 4:77) , Tzitz Eliezer (8:16) and Igros Moshe (2:75) allow Tea and Coffee
- Ra Ovadia Yosef Zatza"l (Yecheve Daat - 2:38) and Halachot ketanot (9) neccesitate alcohol in the beverage, so Tea and Coffee are not allowed
Also, depending on how you rule, the Rema seems to be saying that it is not Lekatchila to use Chamar Medina, but see the MA who rules differently based on the level of the beverage being "Chamar Medina"