The Khazari's question was about humans claiming to have "antiquities and buildings" that were millions of years old.
In other words: Would the fact that some people could prove that advanced civilizations existed millions of years before the Torah's Adam, weaken your faith?
(NOTE: "advanced" is being defined as capable of city building and producing related artifacts of similar and noteworthy complexity.)
The Rabbi admits it would weaken his belief, but since there are no reliable sources of proof for this, it doesn't matter.
The Rabbi even adds that records of merely many tens of thousands of years before Adam would weaken his faith. (not just millions). The Rabbi offers agriculture as an example similar to the Khazari's "buildings".
The OP asks that now that science has such proof, what would the "Rabbi" say?
Science admits that it has no such proof.
"The Neolithic Revolution or Neolithic Demographic Transition, sometimes called the Agricultural Revolution, was the wide-scale transition of many human cultures from a lifestyle of hunting and gathering to one of agriculture and settlement, allowing the ability to support an increasingly large population. Archaeological data indicates that the domestication of various types of plants and animals evolved in separate locations worldwide, starting in the geological epoch of the Holocene around 12,500 years ago. It was the world's first historically verifiable revolution in agriculture."
- Wikipedia, entry: Neolithic Revolution
Therefore, any case of a people building complex artifacts, using agriculture or making buildings never took place many tens of thousands of years ago (let alone millions).
The fact that science does claim that plants, creatures, and inanimate objects, as well as the planets, stars and the universe etc. existed many tens of thousands to millions and billions of years ago, has nothing to do with the question of the OP. The Khazari and the Rabbi are not discussing that. It is a different topic. (The six days of creation contain descriptions, (like evening and morning happening without a sun) which begs the question if it is to be taken literally. For instance, we do not know the "Rabbi's" position on the creation days being 24 modern hours, or rather, epochs of order. However, the post-Adam chronicles of Genesis read like literal history.)
The "Rabbi" could easily point out that science today about the neolithic revolution "starting" "about" 12,500 years ago, (and some scientists in that Wiki- article are quoted as saying that the fertile crescent's neolithic revolution started about 9,000 years ago) is close enough to the Torah's claims for the Adams family.
Medrashim, and Rishonim, have some opinions that show human type creatures existed pre-Adam.
1) Talmud, Eiruvin 18b
2) See Moreh Nevuchim (Rambam's Guide for the Perplexed; Part 1, ch.7)
3) Compare Targum Onkelos: Gen 1:20,21,24 vs. Gen. 2:7
4) Ramban to Gen. 2:7
Eiruvin 18b says, (based on nuance in the text of Genesis 4:25,) that during the 130 years of Adam's separation from Eve, he sired other children. The identity of the mother(s) is not mentioned; but it was not Eve.
The Rambam explains that the sons born to Adam mentioned in the above Medrash, were not really human in the true sense of the word, but were like animals in human form. They did have extra intelligence and were able to be cunning and harmful.
Due to the fact that the Rambam takes this Medrash as referring to literal physical offspring (albeit quasi-human) we must assume that perforce, the mother(s) were female humanoids able to become pregnant from Adam and capable of giving birth. Where did these females, (who could not produce true human children as Eve could) come from? They must have been humanoids created apart from Adam; essentially pre-dating him.
The Ramban to Gen. 2:7, explains that Onkelos held that the Adam species must have first been a living humanoid with its highest level of soul being animal-like in nature. He derives this because Onkelos describes the breathing of a soul into Adam as "Adam became a speaking spirit". This would imply that Adam was alive beforehand, and that G-d only breathed into him the extra soul of human intellect and spirituality. The Ramban concludes that the extra letter "lamed" in the verse, can imply that G-d took a man and changed him so that he became a different man altogether.
According to the above, there is no problem to say that the initial creation of the species "Adam" in Genesis 1, were male and female animal-creatures with better intelligence than animals, yet lacking the full spiritual soul of Adam HaRishon in Genesis 2; who was the recipient of the special creation of the human soul.
(IMHO, this also explains a verse which has bothered me since I was a child. Genesis 4:17 states that Cain built a city. For who?)
Also, science itself is only giving a general starting date for the revolution's beginning. It does not know for certain how long it took to get underway, who did it, what caused it, and if its dating is exact to the thousands place in years.
Science does tell us that tens of thousands to millions of years ago, the human or human-like peoples (creatures) were only capable of the most simple technologies like sharpening stone and starting fire (and living in caves, not buildings) etc. This period is called Paleo-lithic (Old Stone Age) Neo-lithic (New Stone Age) marks the amazing technological revolution of mankind.
In conclusion, we understand the "Rabbi's" position as follows:
The Torah makes significant mention of things in Adam's family history, like farming, animal husbandry, tent living, metal working, city building, and music. It appears that the Torah implies that such developments were just getting started or advancing with the advent of Adam and his offspring. Therefore, a solid proof that such technology was fully advanced and in use by people tens of thousands of years ago, would weaken his faith.
However, in actuality, science now proves that the "Rabbi's" position in front of the Khazari was absolutely correct. :)