Первое приведенное Вами правило — о сложных словах с начальной частью, заканчивающейся на согласную, поэтому к словам с частью вело оно не подходит. Второе было бы применимо, если бы часть вело присоединялась к слову, пишущемуся со строчной буквы, например: велогонки, велобаза, велоспорт, велотренажер. Если же нужно присоединить приставку или первую часть сложного слова к собственному имени, пишущемуся с прописной буквы, то нужно руководствоваться правилом координации. По нему правильно писать вело-Россия, вело-Уфа (аналогичные примеры из правила: спорт-Одесса, фото-Москва). К сожалению, без учета орфографического правила было зарегистрировано название общественного движения «ВелоРоссия».

Архибестия — слово с приставкой архи-, приставка называет высшую степень того, что названо мотивирующим словом.

Архиепископ — слово с приставкой архи-, церковная лексика. Приставка вносит значение старшинства в звании. Подробнее о приставке архи- см. "Русская грамматика", 1980, I, § 469.

 Неофашизм — сложное слово, нео- — связанный корень интернационального характера. Соединительной гласной нет.

Псевдоисторический  — сложное слово, псевдо- — связанный корень интернационального характера. Соединительной гласной нет.

Квазиобъект — сложное слово, квази- — связанный корень интернационального характера. Соединительной гласной нет.

Киноскоп — сложное слово (словарями не зафиксировано, в СМИ встречается как название телепередачи), кино- — корень несклоняемого существительного, -скоп — связанный корень интернационального характера. Соединительной гласной нет.

Археолог — сложное слово, два связанных корня интернационального характера: архе- и лог-. Есть соединительная гласная -о-.

Аэропорт — сложное слово, аэро- — связанный корень интернационального характера. Соединительной гласной нет.

О связанных компонентах интернационального характера подробнее см. "Русская грамматика", 1980, Сложные существительные, §§ 555, 556.

Себестоимость — сложное слово, соединительная гласная -е-.

О терминах "соединительная гласная" и "интерфикс". Интерфикс — это соединительный аффикс ("Русская грамматика", 1980, I, § 56). Основным видом интерфиксов являются соединительные элементы, используемые при образовании сложных слов: -о- (сам-о-лет), -е- (пол-е-вод), -ух- (дв-ух-этажный), -ёх- (тр-ех-этажный), -и- (пят-и-этажный). Так как большинство сложных слов образовано с помощью интерфиксов -о- и -е-, именно эти аффиксы прежде всего изучаются в школе, по традиции их называют "соединительные гласные".