Корректно: Единственное, чего мы не нашли, – это хороший кофе. Подлежащее и сказуемое (единственное и кофе) стоят в форме именительного падежа. Ср.: Чего мы не нашли – так это хорошего кофе.

Грамматические характеристики слова кофе не изменились: это несклоняемое существительное.

Слово кофе пришло к нам во времена Петра I вместе с самим напитком. Как это часто бывает с новыми словами, у него было поначалу несколько вариантов написания и произношения, и со временем наиболее употребительными стали формы кофий и кофей, возникшие под влиянием слова чай (выпить кофея как выпить чая). Эти формы, разумеется, были мужского рода (кстати, в русском языке и сейчас есть слово кофеёк мужского рода). Под их влиянием и слово кофе приобрело мужской род.

Другое дело, что в отличие от слов кофий и кофей существительное кофе несклоняемое. Вы правы: несклоняемые неодушевленные существительные иноязычного происхождения, оканчивающиеся на гласную, в русском языке в подавляющем большинстве случаев относятся к среднему роду, исключения единичны. Поэтому кофе и стремится стать существительным среднего рода. И это нормальный языковой процесс, в истории русского языка есть много примеров того, как слова меняли родовую принадлежность, достаточно назвать хотя бы слово метро, которое было мужского рода (под влиянием существительного метрополитен), а стало среднего.

Но слову кофе «не повезло»: оно попало в тот небольшой список слов (кофе, договор, звонит...), к которым приковано общественное внимание и изменение нормы в которых воспринимается носителями русского языка как признак его «деградации», «порчи» и т. д. Такое негативное отношение образованных носителей языка к этому варианту влияет на его кодификацию: варианты черный кофе и черное кофе пока не признаются равноправными. В словарях мужской род слова кофе дан как строгая литературная норма, а средний род – как допустимое разговорное употребление.

Современные нормативные словари в большинстве своем указывают, что слово кофе, употребляемое как существительное среднего рода (моё горячее кофе), стилистически не нейтрально, эта форма сопровождается пометой разг. (разговорное). При этом кофе — едва ли не единственное несклоняемое заимствование на -е (из тех, что не не обозначают живых существ), которое принадлежит мужскому роду, так что переход этого слова в средний род практически неизбежен. Кроме того, даже в ХIХ веке употребление слова кофе как существительного среднего рода не было такой уж редкостью. См., например: ...молодой моряк очень рассеянно отвечал на вопросы и шутки хозяина; но, к счастью, тот, прихлебывая звездистое кофе, дымя трубкою и пробегая листок купеческой газеты, мало обращал внимания на все, что не носило на себе вида нумерации [А. А. Бестужев-Марлинский. Лейтенант Белозор (1830)]; Появилось кофе в серебряном кофейнике, а за ним вышла красивая мамка в голубом кокошнике с маленьким Вадимом на руках [Д. Н. Мамин-Сибиряк. Приваловские миллионы (1883)].

См. «Горячую десятку вопросов».

Не должны. Употребление слова кофе как существительного среднего рода допустимо в непринужденной разговорной речи, причем на допустимость такого употребления словари указывают уже не одно десятилетие. Впрочем, согласование по мужскому роду от этого не перестает быть предпочтительным: вне обиходно-разговорной речи, в строго литературном употреблении кофе – слово мужского рода.

Слово кофе не изменяется по падежам, а вот устарелое кофей - склоняется, поэтому выражение угостила кофеем (кофейком) принципиально возможно.