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

А вот в том случае, когда географическое название – несклоняемое существительное, его род (в большинстве случаев) определяется по грамматическому роду нарицательного существительного, выступающего в роли родового понятия. Коми, действительно, существительное женского рода (определяем по слову республика), правильно: Золотая Коми. Ср.: Капри – мужской род (остров),  Дели – мужской род (город), но: Миссури – женский род (река).

Оба варианта правильны в единственном числе: банкнот (мужской род) и банкнота (женский род).

Бали может использоваться как существительное мужского и среднего рода. Мужской род – по слову остров, средний род – по внешнему фонетическому облику названия.

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

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

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

Кофе – существительное мужского и среднего рода. Мужской род – строгая литературная норма, средний род – допустимое разговорное употребление. См. также Горячую десятку вопросов.