Faits:
A. X._, ressortissant kosovar né en 1981, est arrivé en Suisse avec ses parents et ses trois frères et soeur en juillet 1991 pour y demander l'asile. Cette requête a été définitivement rejetée le 3 août 1993. L'intéressé a séjourné en Allemagne de 1994 à 1997, avant de retourner dans sa patrie. Il est revenu en Suisse en novembre 1998 afin d'y déposer une seconde demande d'asile, qui a été rejetée le 4 octobre 1999; un délai au 31 mai 2000 lui a été imparti pour quitter le pays. Le 22 avril 2000, il a contracté mariage avec Y._, ressortissante espagnole née en 1980 et titulaire d'une autorisation d'établissement. Il a ainsi obtenu une autorisation de séjour aux fins de regroupement familial. Le couple s'est séparé en décembre 2001 ou janvier 2002; une fille, C._, est née en 2002. Le 3 décembre 2002, l'intéressé s'est vu délivrer une autorisation de séjour CE/AELE valable jusqu'au 27 octobre 2007.
B. Entre 2001 et 2007, X._ a été condamné à plusieurs re-prises, soit en particulier:
- à vingt-cinq jours d'emprisonnement avec sursis pendant deux ans et à 1'400 fr. d'amende, pour violation grave des règles de la circulation routière (ordonnance pénale du 25 juin 2001);
- à trente jours d'emprisonnement et à une amende de 200 fr. avec sursis pendant trois ans, pour lésions corporelles simples et contravention au règlement général de police de la commune de D._; le sursis prononcé le 25 juin 2001 n'a pas été révoqué (ordonnance du 7 mai 2002);
- à une peine ferme de quinze jours d'emprisonnement pour ivresse au volant, les sursis prononcés les 25 juin 2001 et 7 mai 2002 étant main-tenus (ordonnance du 25 septembre 2003);
- à une peine ferme de trente jours d'emprisonnement pour diverses violations des règles de la circulation routière (ordonnance du 8 décembre 2005);
- à une peine ferme de soixante jours-amende, pour violation simple et grave des règles de la circulation, les faits remontant à septembre 2006 (ordonnance pénale du 18 avril 2007).
Au cours de son séjour en Suisse, l'intéressé a occupé divers emplois, notamment en tant que manoeuvre et dans le domaine de la vente. Il a été licencié une première fois en raison de ses absences répétées. Par la suite, il a occupé différents postes peu qualifiés. A deux reprises, il a bénéficié d'indemnités de chômage sur plusieurs mois. Du 1er septembre 2004 au 31 janvier 2007 il est resté au service de la même entreprise, au sein de laquelle il a été promu au poste d'instructeur régional spécialisé. Il a ensuite trouvé un nouvel emploi de durée déterminée, de mai à fin août 2007.
C. Auditionné le 31 octobre 2005 dans le cadre de l'examen de ses conditions de séjour, X._ a déclaré n'avoir jamais repris la vie commune avec sa femme depuis leur séparation. Il a indiqué que les démarches en vue du divorce n'avaient été entreprises que depuis peu, dans la mesure où il s'entendait bien avec son épouse. Cette dernière avait la garde de C._; il voyait la petite une fois par semaine et ne payait aucune pension en faveur de sa femme ou de sa fille mais versait néanmoins 200 fr. par mois lorsque la situation le permettait. Divers membres de sa famille séjournaient en territoire helvétique, à savoir une tante, deux oncles et quatre cousins, alors que ses parents et ses trois frères et sa soeur résidaient "à l'étranger". Entendue à son tour le 6 mars 2006, Y._ a confirmé n'avoir jamais plus cohabité avec son époux depuis leur séparation, tout en expliquant qu'une procédure de divorce n'avait pu être engagée que récemment en raison de difficultés financières. Elle a déclaré que sa fille était heureuse de voir son père un jour par semaine, tout en préci-sant qu'elle ne souhaitait pas reprendre la vie commune. Pour le surplus, elle a corroboré les dires de son mari.
Le divorce des époux X._-Y._ a été prononcé le 28 juin 2006. La garde de C._ a été confiée à sa mère, l'intéressé disposant d'un libre droit de visite tout en étant astreint au versement de contributions d'entretien mensuelles de 600 fr. jusqu'aux six ans de sa fille, 650 fr. jusqu'à l'âge de douze ans révolus, puis de 700 fr. jusqu'à la majorité et/ou l'indépendance financière.
D. Le 2 juin 2006, le Service cantonal a révoqué l'autorisation de séjour CE/AELE de l'intéressé dans la mesure où son mariage n'existait plus que formellement, mais a déclaré être favorable à la délivrance d'une autorisation de séjour annuelle en sa faveur, sous réserve de l'approbation de l'Office fédéral des migrations (ci-après: l'Office fédéral). Il l'a toutefois rendu attentif au fait que ses condamnations pouvaient motiver une expulsion et l'a invité à modifier son comportement.
Le 7 février 2007, l'Office fédéral a refusé son approbation à la prolongation de l'autorisation de séjour de l'intéressé et prononcé son renvoi de Suisse.
Par arrêt du 18 septembre 2009, le Tribunal administratif fédéral a rejeté le recours de X._ contre la décision de l'Office fédéral du 7 février 2007. Il a considéré en substance que l'intéressé et sa fille n'avaient jamais vécu sous le même toit et que leurs liens affectifs et économiques ne pouvaient être considérés comme particulièrement forts. L'intéressé n'avait par ailleurs pas adopté un comportement irréprochable au cours de son séjour en Suisse. Dans ces conditions, la décision querellée ne violait pas l'art. 8 CEDH et X._ ne pouvait en tirer aucun droit à la prolongation de son autorisation de séjour. L'Office fédéral n'avait au surplus ni excédé ni abusé de son pouvoir d'appréciation.
E. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral d'annuler l'arrêt du Tribunal administratif fédéral du 18 septembre 2009 et de dire qu'il a droit à la délivrance d'une autorisation de séjour et de travail. Subsidiairement, il conclut au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Il se plaint pour l'essentiel d'une application arbitraire de l'art. 8 CEDH et reproche à l'Office fédéral d'avoir exercé son pouvoir d'appréciation de façon arbitraire.
Le Tribunal administratif fédéral renonce à prendre position sur le recours et l'Office fédéral propose son rejet.

Considérant en droit:
1. La loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) est entrée en vigueur le 1er janvier 2008. En vertu de l'art. 126 al. 1 LEtr, les demandes déposées avant l'entrée en vigueur de la loi sont régies par l'ancien droit. En l'espèce, la procédure aboutissant au refus de prolonger l'autorisation de séjour du recourant a été initiée avant le 1er janvier 2008. Par analogie, la présente affaire doit ainsi être examinée sous l'angle de l'ancienne loi fédérale sur le séjour et l'établissement des étrangers (LSEE; RS 1 113 et les modifications ultérieures). La procédure est en revanche régie par le nouveau droit (art. 126 al. 2 LEtr).
2. D'après l'art. 83 lettre c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. En principe, il n'existe pas de droit à la délivrance d'une autorisation de séjour ou d'établissement, à moins que l'étranger ou un membre de sa famille vivant en Suisse ne puisse invoquer dans ce sens une disposition particulière du droit fédéral ou d'un traité (cf. <ref-ruling> consid. 1 p. 342 s.; <ref-ruling> consid. 2.1 p. 284 et les références).
2.1 Le mariage du recourant avec Y._, ressortissante espagnole titulaire d'une autorisation d'établissement et dont il était d'ailleurs séparé depuis décembre 2001 ou janvier 2002, a été dissous par jugement de divorce du 28 juin 2006. Le recourant ne peut donc plus tirer de droit découlant de l'accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ALCP, RS 0.142.112.681; cf. <ref-ruling> consid. 8 p. 127 ss). C'est également à juste titre que l'intéressé ne prétend pas à un droit à une autorisation de séjour sur la base de l'art. 17 al. 2 LSEE, ni à une autorisation d'établissement, dès lors que les époux ont vécu ensemble moins de cinq ans (cf. <ref-ruling> consid. 3b p. 147).
2.2 Un étranger peut, selon les circonstances, se prévaloir du droit au respect de sa vie privée et familiale garanti par l'art. 8 par. 1 CEDH, respectivement 13 al. 1 Cst., pour s'opposer à l'éventuelle séparation de sa famille. L'art. 8 CEDH s'applique lorsqu'un étranger fait valoir une relation intacte avec ses enfants bénéficiant du droit de résider en Suisse, même si ces derniers ne sont pas placés sous son autorité parentale ou sous sa garde du point de vue du droit de la famille (<ref-ruling> consid. 1d p. 3; <ref-ruling> consid. 1c p. 84; <ref-ruling> consid. 1c p. 157 et les références). En l'espèce, il n'est pas contesté que le recourant a une fille qui a le droit de résider durablement en Suisse. Par conséquent, il peut se prévaloir des relations qu'il entretient avec celle-ci pour solliciter la prolongation de son autorisation de séjour en Suisse. Dans ces circonstances, il y a lieu d'admettre un droit découlant de l'art. 8 CEDH ouvrant la voie du recours en matière de droit public, étant précisé que, sous l'angle de la recevabilité, il n'y a pas à se demander si ce droit est fondé (arrêt 2C_436/2009 du 1er décembre 2009 consid. 2.1).
2.3 Au surplus, le recours, dirigé contre une décision finale (<ref-law>) rendue par le Tribunal administratif fédéral (<ref-law>), a été déposé en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par le recourant qui a qualité pour recourir (<ref-law>). Il y a donc lieu d'entrer en matière.
3. Le recourant se plaint d'une application arbitraire de l'art. 8 CEDH. Si la motivation de son recours relative à la violation d'un droit fondamental doit certes répondre aux exigences accrues de l'<ref-law>, le Tribunal fédéral revoit toutefois librement l'interprétation et l'application du droit fédéral et du droit international, lesquels comprennent notamment les droits fondamentaux (art. 95 let. a et b LTF).
3.1 Le droit au respect de la vie privée et familiale garanti par l'art. 8 par. 1 CEDH n'est pas absolu. Une ingérence dans l'exercice de ce droit est possible selon l'art. 8 par. 2 CEDH, pour autant qu'elle soit prévue par la loi et qu'elle constitue une mesure qui, dans une société démocratique, est nécessaire à la sécurité nationale, à la sûreté publique, au bien-être économique du pays, à la défense de l'ordre et à la prévention des infractions pénales, à la protection de la santé ou de la morale, ou à la protection des droits et libertés d'autrui. La question de savoir si, dans un cas d'espèce, les autorités de police des étrangers sont tenues d'accorder une autorisation de séjour fondée sur l'art. 8 CEDH doit être résolue sur la base d'une pesée de tous les intérêts privés et publics en présence (<ref-ruling> consid. 2.1 p. 147; <ref-ruling> consid. 2e p. 639; <ref-ruling> consid. 3c p. 5).
En ce qui concerne l'intérêt public, il faut retenir que la Suisse mène une politique restrictive en matière de séjour des étrangers, pour assurer un rapport équilibré entre l'effectif de la population suisse et celui de la population étrangère résidante, ainsi que pour améliorer la situation du marché du travail et assurer un équilibre optimal en matière d'emploi. Ces buts sont légitimes au regard de l'art. 8 par. 2 CEDH (cf. <ref-ruling> consid. 2.2 p. 147 et 153 consid. 2.2.1 p. 156; <ref-ruling> consid. 3b p. 4 s. et 22 consid. 4a p. 24 s.).
Pour ce qui est de l'intérêt privé à obtenir une autorisation de séjour, il faut constater que l'étranger disposant d'un droit de visite sur son enfant habilité à résider en Suisse peut en principe exercer ce droit même s'il vit à l'étranger, au besoin en aménageant ses modalités quant à la fréquence et à la durée (cf. arrêt 2C_171/2009 du 3 août 2009 consid. 2.2). Pour qu'un droit plus étendu puisse exister, il faut notamment être en présence de liens familiaux particulièrement forts dans les domaines affectif et économique (<ref-ruling> consid. 3c p. 5, 22 consid. 4a p. 25; arrêt 2C_617/2009 du 4 février 2010 consid. 3.1). Il faut considérer qu'il existe un lien affectif particulièrement fort lorsque le droit de visite est organisé de manière large et qu'il est exercé de manière régulière, spontanée et sans encombre (arrêt 2A.550/2006 du 7 novembre 2006, consid. 3.1 et les références citées).
3.2 En l'espèce, il ressort de l'arrêt attaqué que le recourant et sa fille n'ont jamais partagé le même toit et que leurs liens affectifs et économiques ne peuvent pas être considérés comme particulièrement forts. Le Tribunal administratif fédéral a en effet relevé que l'intéressé n'avait fourni aucune preuve à l'appui de l'allégation selon laquelle, certains mois, il s'occupait davantage de sa fille que la mère de celle-ci. Dans le présent recours, l'intéressé se contente d'affirmer qu'il exerce son droit de visite de manière aussi large que possible, sans toutefois apporter plus de précisions. Par ailleurs, il n'a pas non plus établi qu'il remplissait régulièrement ses obligations financières à l'égard de sa fille; il n'a joint aucun moyen de preuve, même pas une attestation de son ex-épouse, qui aurait pu confirmer qu'il contribuait régulièrement à l'entretien de son enfant. C'est donc à juste titre que le Tribunal administratif fédéral a considéré que la relation entre le recourant et sa fille n'excédait pas le cadre des liens existant en général entre un père et son enfant, lorsque ceux-ci ne vivent pas sous le même toit. Le recourant ne peut dès lors pas disposer, comme il le souhaite, d'un droit de séjour découlant de la seule présence de sa fille en Suisse. Il devra se contenter, ce qui est encore conforme aux exigences de l'art. 8 CEDH, d'exercer son droit de visite depuis l'étranger, les modalités quant à la fréquence et à la durée devant être aménagées en fonction de cette situation. Compte tenu de la distance qui sépare son pays d'origine de la Suisse, il est indéniable que son départ rendra l'exercice du droit de visite plus difficile, sans toutefois y apporter d'obstacles qui le rendrait pratiquement impossible dans le cadre de séjours à but touristique.
3.3 A cela s'ajoute que le recourant ne peut pas se prévaloir d'un comportement irréprochable. A plusieurs reprises, il a violé les règles de la circulation routière et conduit en état d'ébriété (cf. let. B ci-dessus). En dépit des multiples condamnations dont il a fait l'objet, des peines fermes prononcées à son encontre ainsi que des avertissements du Service cantonal quant aux conséquences de son comportement, l'intéressé n'a pas pris conscience de ses actes, ou alors très tardivement puisque la dernière condamnation porte sur des faits remontant à décembre 2006.
3.4 L'intéressé fait grief au Tribunal administratif fédéral de n'avoir pas suffisamment tenu compte, dans la pesée des intérêts, de la durée de son séjour en Suisse, de son intégration sociale et professionnelle ainsi que sa parfaite maîtrise du français et de l'allemand. Ces éléments ne suffisent cependant pas à justifier un droit de séjour découlant de l'art. 8 CEDH et ne compensent pas l'absence de liens familiaux particulièrement forts du recourant avec son enfant. Au demeurant, il a été constaté que son intégration professionnelle n'était pas spécialement réussie et que sa situation financière n'était pas saine, l'intéressé ayant fait l'objet de plusieurs poursuites ayant débouché sur des actes de défaut de biens.
Dans ces conditions, il y a lieu d'admettre que l'intérêt du recourant à demeurer en Suisse ne l'emporte pas sur l'intérêt public à son éloignement. Le Tribunal administratif fédéral a donc correctement interprété et appliqué l'art. 8 CEDH en retenant que le recourant ne pouvait prétendre à la prolongation de son autorisation de séjour.
4. Enfin, le recourant ne peut pas faire valoir de droit à une autorisation fondée sur l'art. 4 LSEE, de sorte que la voie du recours en matière de droit public n'est pas ouverte sur ce point (art. 83 let. c ch. 2 LTF; cf. ATF <ref-ruling> consid. 2.1. p. 284; 388 consid. 1.1 p. 389 s. et les références). Il ne sera donc pas entré en matière sur les critiques relevant d'une application "arbitraire" de l'art. 4 LSEE.
5. Il résulte de ce qui précède que le recours doit être rejeté dans la mesure où il est recevable. Succombant, le recourant doit supporter les frais judiciaires (art. 65 et 66 al. 1 LTF) et n'a pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux participants à la procédure et au Tribunal administratif fédéral, Cour III.
Lausanne, le 7 mai 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Zünd Mabillard