I think there are two separate questions.
(1) When were there people who were physically capable of a 4-minute mile?
(2) Did any of them actually do it?
For the first question, I think it's possible that prehistoric men were occasionally in that kind of shape, but I'd guess it would have been extremely rare. I doubt they had the combination of training required, except for the occasional genetic freak. For instance, I would guess that the Tarahumara don't have any sub-4 runners even though they all run, because they all run long and slow. As for the 1700s-1800s, it seems likely that, if there were runners focused on training to race relatively short (e.g. one-mile) distances, then they could have been in around 4-minute shape, but not many of them.
Would love to hear some historical facts bearing on the above.
For the second question, prehistorically I'd bet the answer is "no". It would require an amazing coincidence. Persistence hunting would not involve all-out chases of that length. Even if someone was running all-out, a sub-4 mile by even a very fit person would require some pacing and knowledge of the distance to go. Even granting that, you'd need it to happen for a distance of between 1609.344m and probably 2000m (beyond that it seems extremely unlikely). However, people have been around for a long time so I guess you never know. As for in the more modern era, 1700s-1800s, I don't know enough about the history to know if the legends are believable or not, but it seems at least a little plausible.