To answer this question, we'd need to know how fast a flying reindeer-drawn sleigh can go, as well as how long on average it takes Santa to climb down a chimney and drop off presents at a house. Once we know these figures, we'd still need to solve a Traveling Salesman algorithm to find the fastest route Santa could take between every house in the world. Unfortunately, that's an NP-hard problem, meaning modern computers can't provably solve it, though they can find a decent route (if not the best) given enough time.

But for some oversimplified figures, here's a graph of estimated world population over time. As early as 3,000 BC, there were over ten million people in the world. Assuming a tenth of them were "children" by whatever standard we're using (almost certainly an underestimate, given how quickly the population was growing), we have a million children. Assuming Santa can deliver as long as it's 25 December in any timezone (though neither Christmas nor the modern calendar nor timezones existed in 3000 BC), he has just under 48 hours to complete his mission. 1,000,000 children divided by 48 hours means that in 3000 BC, he'd already need to, on average, travel between and deliver to 5.8 children per second. And, he'd only need to get faster as time moves on and the population significantly grows.

Currently, as many people know, it would be quite impossible for Santa to deliver presents to the large world population.

It would be a challenge for Santa to deliver presents across an ordinary town if you imposed more realistic limitations on his method of travel. Even if he could get down to a rate of 1 child per minute (so already absurdly unrealistic), there are only 1440 minutes in a day. So that gives you an idea of just how small a human population would have to be.

There had been millions of humans spread out across the planet well into prehistoric times. Maybe /r/AskAnthropology can help you find a human population bottleneck early enough for Santa to complete his mission?

As has been pointed out, it wouldn't have been possible to give a gift to every human child, but even now he would only need to give one to every child that believes in him. I would guess that it would have become impossible even in the lifetime of the original Saint Nicholas.