In conversations between theists, agnostics and atheists, this question is posed reasonably often, often phrased as:
"What would convincing evidence of god look like?", or "What would convince you of the existence of God?".
One of the most sensible answers I've encountered to this question goes along the lines of:
"I don't know, but if an omnipotent, omniscient god exists, it would presumably know how to persuade me of its existence. The fact it has not done so suggests that if such a god exists, it has decided not to persuade me".
If this is a reasonable response, it doesn't necessarily say anything about whether we can ever discover a god without that god's intervention, but in hundreds of hours spent listening to conversations between theists and atheists, I have have yet to encounter an explanation of how this might happen, so I share your curiosity.
I have friends who claim to know that a god exists because they have a personal relationship with "him". They are unable to provide me with anything from that relationship which convinces me that their relationship is real, but that on its own does not constitute proof that they are wrong.
Being convinced though is clearly a distinct state of affairs from being convinced because of evidence. We have all likely at one time or another been persuaded of something in the absence of what might be called reasonable evidence (even when we perceive that such evidence has been presented). Part of the problem is that we know our minds are capable of deep, profound delusion, so even phenomena which appears to confound our understanding of the 'natural order' - such as a sea parting and a lone figure walking up from the ocean floor to announce his divinity - might be attributed to misperception (as might the corroborating 'evidence' of a thousand simultaneous onlookers). I am not saying that I would not be persuaded by such an event. I might well be. But that's not to say I should be persuaded, especially when one considers that there is also the argument that any such act might be an act of deception by a sufficiently powerful entity; one who is immensely powerful advanced but does not meet the definition of the god of which we conceive.
My lack of ability to imagine, locate or accept any evidence returns me to the notion that if an 'omni-god' wants me to know of it's existence, I will know, and in the meantime there is nothing I can really do about it, other than to follow the advice of Christian friends and to sincerely ask for such an enlightenment, which has not to date been forthcoming.
To address previous answers: Many, many Christians would claim that God simultaneously exists outside what we know of 'nature' and intervenes within it, whether by miracles or the aforementioned 'personal relationship'. Whether metaphysics can be addressed by science does not necessarily impact upon whether a god might be able to demonstrate its existence in our realm, especially if that god is credited with creation of the physical world.
As to omnipresence, I don't see how the presence of something everywhere should necessarily alert us to its presence, unless by 'everywhere', our perception/'knowledge' is deemed a location (which would likely be debated by atheists and theologians alike). There are various theological positions on the nature of how the 'omnis' are to be construed, including some which are likely created to circumvent objections that arise when they transgress principles of logic.