I’d like to say “when are you free except Tuesday?”. Is it grammatically correct?
It is pretty clear what you are asking. There are really two sentences here "When are you free?" is the question, and "You can say any day except Tuesday." is a clarification to the question. You've then reduced the second sentence and merged it with the first. It is the sort of thing that is common enough in casual speech, or even in emails.
To be grammatical you need to use "except Tuesday" to modify "day" and not "free".
So you could say "What day, except Tuesday, are you free?"
But what you really want to say is "I'm free on any day except Tuesday. When are you free?"