Hi,
I know it's been awhile since you posted this, but it is possible John McKenzie's family didn't really settle in Newfoundland in the traditional sense. During the 18th century, much of the population of Newfoundland was fairly transient, coming over to fish for the summer, and returning in the fall.
Alternatively, Seary's "Family Names of the Island of Newfoundland" lists a Dugale Karr McKenzie, soldier of St. John's in 1779 as an early instance of the name. Maybe John McKenzie's father was stationed in St. John's as part of the garrison or the navy? Sort of fits, since John went on to become a solidier himself.
You could also try contacting the Maritime History Archive and see if there is a McKenzie file in the Matthews Name Files.
Jennifer.