It only depends on whether there are catchable fish in the ocean. There is plenty of evidence that very early humans (even non-humans, like Neandertal and Heidelbergensis (the predecessor of both Neandertal and Homo Sapiens)) knew how to tie nets and make flint knives and spears; and archaeologists have found carved animal bones that may have served as fish barbs (for spear points) and fish hooks from "prehistoric" (pre-technological) humans ten thousand years ago. Take a chunk of hard femur and use a rock or sharp flint to pare it into a shape you want. What else were you doing today anyway?
Fish alone, even raw, can supply enough protein and nutrients (eat the brains, eyeballs and organs) to keep humans alive for many years; no vegetables needed.
All you need next is seaworthy rafts and an ability to dive and swim; also in evidence from prehistoric times. See Thor Heyerdahls's Voyage of the Kon-Tiki, for example.
Also note that such rafts can be HUGE, the size of several football fields; and with pitch (waterproof tar widely used in prehistoric construction) and strong hair rope (animal or human hair), many smaller rafts can be made (say 10 yards square) and lashed together, making a resilient, flexible surface that is nearly impossible to overturn or sink. Especially if the inner material (I say inner because I presume it is covered by pitch) is reeds and wood that naturally floats; the platform may be swamped by a wave but will rise to the surface again anyway.
Such rafts can have shelter from the sun and precipitation built on board. Fresh water would be a distinct problem, but large skins full of fresh water are buoyant enough to be easily towed, and it is possible to capture rainfall in the ocean. Also water can be obtained through food metabolism (see here), basically fish blood has the same salinity as terrestrial blood, so does not create a salt-elimination problem for us.
Although I have never heard of any archaeological evidence of it, I think solar stills to distill seawater might be within the scope of prehistoric human technology, it isn't like they never saw water evaporate or condense. If nothing else, they could learn to follow the rain.
The answer is: Sea faring cultures could abound and live on the sea for years at a time, plenty of time to find other lands and colonize them, without any need for a terrestrial path, or any technology more advanced than what we have evidence for actually existing in prehistory.
Response to Comments about Raft Size
See The Benson Raft, as an example; circa 1906, a gigantic sea worthy cargo raft made of logs (tied together with chains not available to primitive people, but still, giant rafts of logs **can be ** seaworthy).
Here is an article on Pre-Columbian Rafts, made of bundled Reed and wood, often bamboo, these are tied together by hemp, and which mentions they were found as much as 36 feet long, with over 30 men, and 30 ton cargo capacity. Spanish explorers in the 1500's encountered them, and reported the rafts were almost unsinkable; because the were constructed so water just washed through them.
Note these particular rafts in South America only lasted six months to a year, but were not coated in pitch like early Egyptian rafts, which lasted for many years.
In my commentary response I discuss using timbers to make rafts, which I consider viable. Bamboo is another very popular alternative and seaworthy.
But rafts are not the only option: early sailing ships where constructed of timbers with pitch or tar for waterproofing, and iron or metal is never a necessity in wood-working. We have all heard of dove-tail joining; and woodworkers can create dozens of similar locking mechanisms to join wood by simple carving; I have seen an hourglass kind of join for joining boards edge to edge, for example.
The question isn't necessarily about the materials or the shape of the ship, just whether primitive humans could build something to live on the ocean for years. All oceans, if heated by a sun, will have convection patterns that circulate between continents. An ocean-going tribe caught in a storm might well find themselves on something like our Gulf Stream and transported to another continent, which they might choose to colonize, especially if they are the first intelligent species to set foot there, and don't want to risk trying to find their way home (Ocean streams are one-way streets, the one that brought you to point B won't take you back to Point A.)