Being a methodological naturalist does not necessarily mean commitment to deduction of definite predictions and pursuit of rigorous testability. (After all, many so-called natural sciences do not, including much of biology, as far as I know.) Adopting the "Guess-Compute-Compare" method, as Feynman puts it, does.

Chomsky's "methodological naturalism" is "counterposed to "methodological dualism": the doctrine that in the quest for theoretical understanding, language and mind are to be studied in some manner other than the ways we investigate natural objects, as a matter of principle." (Chomsky 1995: 28) Chomsky's naturalist approach is thus consistent with his stance over the years against the importance of methodology (not only for hypothesis-formation but also for hypothesis-testing, I understand), as stated in Chomsky 1988: 190, for example. See Schütze 1996: 210, footnote 1 for related remarks.

Chomsky, Noam. 1995. "Language and Nature," Mind 104: 1-61.
Chomsky, Noam. 1988. Language and Problems of Knowledge: The Managua Lectures, MIT Press, Cambridge, MA.
Schütze, Carson. 1996. The empirical base of linguistics: Grammaticality judgments and linguistic methodology, University of Chicago Press, Chicago.