I originally thought that this paradox would only arise when the speaker was known to be fallible. The reason you can't know beforehand what day the exam will be, is because when running through the reasoning, you come to suspect that what the teacher said is false. But what if the teacher was known to be infallibly truthful? Imagine it is God that makes the announcement (and suppose we know that God cannot speak falsehoods). My thought was that the announcement would then simply be false, i.e. the exclusionary argument proves that this statement could never be made by a being known to be infallible.
But I've changed my mind about this. It seems that if God were to make such a statement, we would be thrown into confusion by it, and would be unable to work out on what day the surprise exam would be. So the statement would turn out true, even though we know the speaker is truthful and so cannot (unlike before) suspect that there will be no exam. (But then what's wrong with the exclusionary reasoning? Most puzzling!)
A commenter over at Opinatrety distills the core of the problem:
I have a coin in my hand. But you will never know if I really have a coin in my hand before I open it.
So you do not know if I have a coin in my hand or not. Then, I open it. Yes, there is a coin. My statements are right.
As he notes, the trick lies in saying 'you will never know'. By saying that, you throw the listener into a state of epistemic conclusion, thereby ensuring the truth of that very statement. Even the known-infallible God could do this, by saying to you: "X is true, but you cannot know it". After all, you'd then reason, "If God says I cannot know X, and he's never wrong, then there must be something dodgy about it... I'd better suspend belief" -- so then you don't know X any more! Even though you were told it from an infallible source! Tricky.