Well, just to make my argument simpler, let's say that he does not break ties randomly, but instead does it alphabetically.  If two or more suits are tied for most number of cards remaining, then he picks the first one in alphabetical order.  This clearly has the same minimum as a random tie-breaking rule.  

So his first guess is a club.  At worst, no other suit will ever have more cards remaining.  He will guess clubs on every turn, and will wind up with 13 correct guesses.  This is very low probability.

More likely, at some point some other suit (or suits) will have more cards remaining in the deck.  At that point, there will be n clubs remaining and n+1 of the other suit (or n+1 of each of the other suits).  He already has 13-n correct guesses, and he can guarantee n+1 more if he has to keep guessing the new suit.  So he will get a minimum of 14.  In fact, his final total will be 13 + k, where k is the number of times he was able to abandon the suit he just guessed for a suit that had more cards remaining.  Thus, his minimum is 13, but he will likely do a lot better.  I am not ready yet to say how much better.

In general, if there are c cards remaining, his minimum correct guesses are c/4, rounded up to a whole number.