IMO, Tolkien believed that the "long defeat" was embedded in the world from the beginning, and nothing could ultimately change that. But much of the specifics of what people do and say, throughout that immeasurably long span of time, is the product of free wills. Only occasionally do his characters get explicitly commandeered by the Valar......there's a combination of free will and fate at play...Bilbo and Frodo, exercising free will, showed Gollum mercy. And Gollum destroyed the Ring. But the grand sweep of it all (not the fine details) was written in the Music...
Basically, it's like the difference between (and reconcilation of) quantum mechanics and gravity. It's all crazy and detailed and unpredictable under the surface (where free will comes in), but when you zoom waaaay back, it's all rather smooth and simple like gravity (which is where fate comes in)...
In other words, Tolkien was a string theorist. There, I said it.
Eg. The Doom of Mandos was written, and nothing could change that. But the characters who participated in its fulfillment were free to not participate in its fulfillment. Therein lies the reconciliation of free will and fate.