I've thought about this. Ignoring that Paul said "who can come to God if no-one preaches, and who can preach if no-one sent him?", and that the hypothesis requires there to be no history...
I might have experienced something beautiful or awe-inspiring, and maybe also have realised that death is universal. I would have asked myself: why is this? Nobody taught me how to appreciate beauty or how to accept love or ordered me to die - yet it has such a profound affect on me, life-changing effects. You can't know love if you don't experience it. How are we different from animals - they are also alive, but they don't work or display any responsibility towards anything other than themselves. Life as a universal truth might have a universal significance or meaning. Of course, only if I have experienced love will I be able to know its worth. But once I have experienced genuine, unselfish love, I would have known how it inspires meaning. Why do some people go through great lengths and personal pain to keep loving, while others simply don't bother at all? All of this would only have created the possibility of a common or higher meaning. Only under those circumstance would I have realised that if I were the only human being on earth, my life would still have that same meaning, otherwise what I feel now would be false. Since only only love has made me experience this meaning, something or someone might have provided the 'original' love. The truth of experience must remain equally true even after the experience has passed, and by implication even before it has happened.
Considering that the earliest religions were pretty empty - they basically had a god for everything, explainable or unexplainable - I think people have an inherent and natural affinity for spirituality and belief, although maybe not for faith. We distrust everything because we are aware of our own unreliability. Whatever started the movement towards a montheistic religion must have had a pretty strong case, because the idea of only one all-powerful god is less 'humanly reasonable' than the idea of many. The oldest religious systems, Hinduism and Buddhism, have no clear concept of 'god', but very specific ideas about human nature. There is nothing wrong with their humanity, especially in buddhism, but there is really no god in the picture, no real need for a god, only the acknowledgement of a godly nature.
Having imagined the possibility of a god, I would ask myself what role he would have played in my existence. Clearly a god must be supernatural, because nature is definitely not in charge of this planet, or the universe for that matter. God would know me and love me, and also tell me what He expects from me. I would by now have realised that betraying love leaves a mark on my conscience, a feeling of having wronged the hand that feeds me, and the realisation that I do not deserve that love, that the lack of it will be like punishment justly deserved. But having experienced that the love does not punish me, I will be conscious of a suspended punishment, fearful that at any stage my wrongdoing might come back and bite me in the ankle. If the orginal source of love is God, then I am ultimately responsible to God for my lack of love. This responsibility is about the closest I would be able to get on my own initiative. Otherwise the whole concept of a god falls flat, and once again I am only responsible to myself. This will however deny the love that I have already received. The best I would be able to do is to try to earn that love.
My search for God would have led nowhere if God did not come down to earth to make Himself known. I can't deny that I know God because I know Jesus (who was the face of God) through the collection of accounts called the Bible. Ther is no getting past the fact that God is a historical God, "the God of Abraham, Isaac and Jacob", a present with Him is the same as a past and a future with Him. My experience of his love has left no doubt about God's existence, and my utter inability to know Him except though what I see spiritually. I would have lived in fear of God if it were not for Jesus who died in my place, and provided the only way of knowing God. I would always have tried to earn God's love, and follow His rules knowing I would slip up sometime. Pain has disciplined me and perseverence has strengthened my character. Now that I have reason to trust God I have reason to hope that death isn't final, because what can anyone do worse than killing me. Surely God's mercy is greater than any person's punishment?
11Since, then, we know what it is to fear the Lord, we try to persuade men. What we are is plain to God, and I hope it is also plain to your conscience. 12We are not trying to commend ourselves to you again, but are giving you an opportunity to take pride in us, so that you can answer those who take pride in what is seen rather than in what is in the heart. 13If we are out of our mind, it is for the sake of God; if we are in our right mind, it is for you. 14For Christ's love compels us, because we are convinced that one died for all, and therefore all died. 15And he died for all, that those who live should no longer live for themselves but for him who died for them and was raised again.
16So from now on we regard no one from a worldly point of view. Though we once regarded Christ in this way, we do so no longer. 17Therefore, if anyone is in Christ, he is a new creation; the old has gone, the new has come! 18All this is from God, who reconciled us to himself through Christ and gave us the ministry of reconciliation: 19that God was reconciling the world to himself in Christ, not counting men's sins against them. And he has committed to us the message of reconciliation. 20We are therefore Christ's ambassadors, as though God were making his appeal through us. We implore you on Christ's behalf: Be reconciled to God. 21God made him who had no sin to be sin for us, so that in him we might become the righteousness of God.