Насколько древним является почитание Бога?

Если хотите знать о первом священнослужении Господу, то это - принесение Ему жертвы. Вот, как это описывает бытописатель:

Адам познал Еву, жену свою; и она зачала, и родила Каина, и сказала: приобрела я человека от Господа. И еще родила брата его, Авеля. И был Авель пастырь овец, а Каин был земледелец. Спустя несколько времени, Каин принес от плодов земли дар Господу, и Авель также принес от первородных стада своего и от тука их. И призрел Господь на Авеля и на дар его (Быт.4:1-4).

Позднее, при прор. Моисее, это жертвоприношение было усложненно и детализировано Богом, превратилось в настоящее богослужение. Преемницей иудейского богослужения стала христианская Церковь.

Что же касается Мельхиседека, то вот что о нём пишет ап. Павел:

Ибо Мелхиседек, царь Салима, священник Бога Всевышнего, тот, который встретил Авраама и благословил его, возвращающегося после поражения царей, которому и десятину отделил Авраам от всего, – во-первых, по знаменованию имени царь правды, а потом и царь Салима, то есть царь мира, без отца, без матери, без родословия, не имеющий ни начала дней, ни конца жизни, уподобляясь Сыну Божию, пребывает священником навсегда. Видите, как велик тот, которому и Авраам патриарх дал десятину из лучших добыч своих (Евр.7:1-4).

Очевидно, о нём было известно только то, что написано в кн. Бытия. Оттуда видно только, что он приносил жертвы Истинному Богу, а не демонам, как язычники. Таким же священником Богу был и прав. Иов, он тоже приносил жертвы Истинному Богу, но не был потомком Авраама. Полагают, что он был его племянником, сыном Нахора:

Был человек в земле Уц, имя его Иов; и был человек этот непорочен, справедлив и богобоязнен и удалялся от зла (Иов.1:1).

Только при прор. Моисее священство становится отдельной кастой - это сыновья его брата Аарона. Лишь они теперь имели право приносить жертву Богу.

Однако о Мельхиседеке есть ещё одно мнение:

Мелхиседек был Сим; он по величию своему был царем, как родоначальник четырнадцати племен, но также и первосвященником, потому что по преемству приял священство от отца своего Ноя. Сим жил не только до времен Аврама, как говорит Писание, но даже до Иакова и Исава, сынов Аврамова сына. Его ходила вопрошать Ревекка, и Сим сказал ей, что два народа во чреве ее, и старший поработает младшему (Быт. 25:22-23). Но Ревекка не пошла бы вопрошать его мимо мужа своего, который так чудесно спасен от заклания, и мимо свекра своего, которому так часты были Божественные откровения, если бы не знала о величии его от самого Аврама и сына его.

И Аврам не принес бы Мелхиседеку десятины, если бы не знал, что он несравненно выше его. Нельзя подумать, что кого-либо из Хананеев или Содомлян вопрошала бы Ревекка, и что кому-нибудь из них Аврам принес бы десятину возвращенного им достояния. Поскольку дни жизни Мелхиседека простирались до времен Иакова и Исава, то вероятно сказанное, что Сим и являлся им. Отец его Ной жил на востоке, Сим же обитал среди двух поколений, то есть среди сынов Хамовых и своих сынов, составляя как бы преграду между тем и другим племенем, ибо опасался, чтобы потомки Хамовы не увлекли его сынов в идолопоклонство (толкование прп. Ефрема Сирина).

Есть и другие мнения, которые можете найти в толкованиях святых отцов по ссылке.