From season 1, John Locke is regarded as the best hunter and tracker amongst the Losties. However, he admits that he only learned some basic skills like tying knots and identifying birds as a Webelos scout, meaning he quit the scouts in fourth or fifth grade. We know he learned some very basic hunting skills while hunting birds with his father, but none of this matches up with the advanced skills he seems to have on the island. Many of his skills surpass what he can simply read about in books without at least some hands-on experience.
In addition to the things you mentioned, the episode Walkabout implies that Locke performed extensive research on wilderness survival prior to his trip to Australia.
RANDY: So, you wander around hunting and gathering food, right? On foot?
LOCKE: Not that you would understand, but a Walkabout is a journey of spiritual renewal, where one derives strength from the earth. And becomes inseparable from it. I have vacation days, I'm going, Randy. I've already made a reservation.
AGENT: The Walkabouts we arrange here are not just some stroll through the park. It's trekking across vast stretches of desert, rafting bloody treacherous waters.
LOCKE: Look, you've got no idea who you're talking to. I'm well aware of what's involved, believe me. I probably know more than you on the subject.
He also did some hunting doing his time in a commune, as seen in Further Instructions. We also see that he considers himself a hunter.
EDDIE: I'm sorry, John, but you're not going to shoot me. You're not a murderer. You're a good man. You're a farmer.
LOCKE: Nope. Not a farmer. I was a hunter. I'm a hunter.
Additionally, the episode Cabin Fever presents the possibility that Locke has some sort of innate connection to knives and compasses, which could represent hunting and tracking/navigation.
RICHARD: I want you to look at these things... and think about 'em.
[He places some items on the table.]
RICHARD: Okay, now tell me, John, which of these things belong to you?
JOHN: To—to keep?
RICHARD: No, no, John. Which of these things belong to you already?
[John takes a vial of some kind of substance, a compass and after a pause, a knife.]
RICHARD: Are you sure the knife belongs to you, John?
The official reference book The Lost Chronicles states that Locke
Is seemingly in tune with the island's mysterious forces...
It isn't explained perfectly, but it does become a little more believable.