RASHI refers to the snake as "HeAtid L'Klalah", which means the one who in
the future would be cursed, but not "destined" to be cursed. As in many
other instances - and this is a subtle but important area of Jewish thought
- HaShem was anticipating what would happen but not forcing the event to
occur. Hence, no contradiction to free will.
RASHI is telling us the reason why HaShem waited until now to bless the
animals: Had He blessed them all when they were created, He would not have
then gone back and cursed the NACHASH, despite the sin that He anticipated
would occur. He wanted to leave open the option of cursing the snake should
it sin, but was not locking it in to sin.
However, one could still legitimately wonder why the NACHASH was cursed.
Avraham Ibn Ezra (a classic early commentary) discusses this issue at
length, rejecting the possibility that NACHASH was a reference to the
Yetzer HaRa or the Soton (if so, was the Soton cursed to crawl on its
belly, etc?) and that the snake never spoke, but an angel spoke to Eve
through the the snake (If so, what did the snake do? Why was it punished?).
The Ibn Ezra concludes that the snake walked upright, was on a higher level
of cognition than any other created thing except for man, spoke, and
presumably had free choice.
This interprtation has its own difficulties (other commentators are
reluctant to accept that the snake could actually speak and would point out
that loss of mental ability was not one of the curses to the snake), but if
you're looking for an address for your question, look at the Ibn Ezra.
David Hojda