Well, not necessarily. Of course these and other paradoxes are why people assume there just has to be something preventing time travel even if as things stand we do not know how it is prevented.
Nevertheless, you can come up with possible answers to your problem.
For one you could assume we live in a multi-verse (which is a supported, albeit not popular, interpretation of Quantum Mechanics). In short there is a universe where you have a tuna sandwich and another Spaghetti-O’s and another a PB&J and so on. Free will is preserved. Which you choose to do just throws you on that new world line (and you are time traveling not in time but between different universes).
For another, and this one will hurt your head, while you have free will you will always “remember” what you do.
For instance, you go back in time and say “Blah blah blah” to your past self. The future you will remember saying that so you decide to go back and say “Yadda yadda yadda”. Thing is the future you will now instantly (and with no clue otherwise) remember that you said “Yadda yadda yadda” to your past self. In short whatever you choose to do is what you will remember doing.
Works the other way too. You travel forward and see the tuna-eating you. So you decide to have Spaghetti-O’s instead. So now you will remember seeing you eating Spaghetti-O’s. Again you have free will but whatever you choose to do is what you will remember doing.
Ack…I think I just popped a blood vessel pondering the implications of that. 

)