Faits: A. X._, né en 1973, a été admis à suivre les études de licence en gestion d'entreprise auprès de la Faculté des sciences économiques et sociales (ci-après: la Faculté) de l'Université de Genève à partir du semestre d'hiver 2002-2003. A l'issue de la session d'examens d'été 2007, le prénommé a été exclu de la Faculté, au motif qu'il avait échoué après deux inscriptions à un même enseignement (procès-verbaux d'examens des 21 septembre et 31 octobre 2007). A l'encontre de cette décision, X._ a formé une opposition qui a été rejetée par décision du doyen de la Faculté du 7 mars 2008. X._ a déféré ce prononcé à la Commission de recours de l'Université de Genève, qui l'a débouté par décision du 7 novembre 2008. Cette autorité a considéré que "le recourant, après avoir échoué à l'examen de 'méthodes statistiques' en 2006, s'est réinscrit à cet enseignement l'année suivante et s'est présenté à l'examen à deux reprises, en obtenant une note inférieure à 4 qu'il ne pouvait au demeurant plus valider, ayant déjà épuisé cette faculté". Le recourant n'avait ainsi pas obtenu les crédits correspondants au cours de "méthodes statistiques" après deux inscriptions à cet enseignement et se trouvait ainsi exposé à une décision d'élimination, en vertu du règlement d'études. En outre, le recourant ne faisait valoir aucune circonstance exceptionnelle en relation avec son échec répété au cours en question, qui aurait pu conduire à ne pas prononcer son élimination. B. A l'encontre de ce prononcé, X._ interjette un recours au Tribunal fédéral. Il demande en substance d'annuler cette décision et, principalement, d'inviter la Faculté à lui délivrer le diplôme de licence, subsidiairement, de l'autoriser à se présenter à nouveau à l'examen portant sur le cours de "méthodes statistiques". Il dénonce une mauvaise application du règlement d'études ainsi qu'une violation de son droit d'être entendu. L'autorité précédente s'en rapporte à justice quant à la recevabilité du recours; sur le fond, elle persiste dans les considérants et le dispositif de sa décision. L'Université de Genève s'en remet à justice s'agissant de la recevabilité du recours et conclut à son rejet sur le fond. La Faculté ne s'est pas déterminée. 