It is, in fact said in the Silmarillion that "to men, (Ilúvatar) gave strange gifts" which tends to suggest that there is a predestination to the world, and humans are the "wild cards in the deck", who can supersede this. (I could walk a flight of stairs, roust my house guests, and return with the page number, but any Tolkien buff who has read the Silmarillion 9 times or more as I have can just as easily find it in his own copy).
I suspect all races have free will over immediate situations, but in the end, the "Music" has a predeterministic element to it, and that men represent chaos theory to the Music of the Ainur, composed by Ilúvatar.
Of interest is that Túrin Turambar named himself "Master of Fate" and yet he played into his own fate is a very fateful way (Shakespeare would be proud, and I sure hope there's a "Mandos" in which Mr. Tolkien and Mr. Shakespeare collaborate.) of saying that sometimes we alter the design, sometimes we play into it, despite our best efforts and intentions (Interesting note is that Mr. Tolkien puts Túrin on the head of his Karmic hero scale, he will save the world in the last battle (and chase Morgoth up a pine tree?))
One relevant text that has always fascinated me is the tale of Finrod Felagund (by far the coolest of all elves, no citation needed) discussing the origin, fate, and nature of men with a wise (wo)man (from the house of Bëor? - again, I have guests in my library, feel free to help me out with citation) Felagund touches on the original nature of man (with references to original sin), and that man has adopted a different fate, fallen from its original intention that men should never die. This is an "Arda marred" concept that suggests that the spiritual nature of men is not less, but far greater than that of the Elves, but has fallen. References are vague, and tend to a darkness that men have left behind, and do not speak of - a literary device in which Tolkien uses vagueries to speculate on the spiritual nature of man.