Sachverhalt:
A. Der libanesische Staatsbürger X._ (geb. 1972) heiratete am 2. September 2002 die Schweizer Staatsangehörige Z._ (geb. 1966). Er erhielt zunächst eine Aufenthaltsbewilligung und im Herbst 2007 die Niederlassungsbewilligung für den Kanton Zürich. Ein Gesuch um erleichterte Einbürgerung ist hängig.
Die erste Ehe von X._ mit W._ wurde am 31. März 2001 resp. 19. Februar 2002 im Libanon geschieden. Die aus dieser Ehe hervorgegangene Tochter Y._ (geb. 25. Dezember 1996) reiste am 8. Oktober 2006 mit einem bis zum 21. November 2006 gültigen Besuchervisum in die Schweiz ein. X._ stellte am 27. Oktober 2006 für seine Tochter ein Gesuch um Aufenthaltsbewilligung im Familiennachzug, obwohl er zuvor zugesichert hatte, für die fristgerechte Wiederausreise seiner Tochter zu sorgen. Die Sicherheitsdirektion des Kantons Zürich wies das Gesuch mit Verfügung vom 12. Juni 2007 ab und setzte Y._ eine Ausreisefrist bis zum 31. Juli 2007.
Dagegen liessen Y._ und X._ mit Eingabe vom 12. Juli 2007 Rekurs an den Regierungsrat des Kantons Zürich erheben. Mit Beschluss vom 8. Juli 2009 wies der Regierungsrat den Rekurs betreffend Aufenthaltsbewilligung für Y._ ab. Eine hiergegen am 21. September 2009 erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich, 4. Kammer, mit Urteil vom 30. Dezember 2009 ab.
B. Mit Eingabe vom 8. Februar 2010 erheben Y._ und X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen, der Entscheid des Verwaltungsgerichts vom 30. Dezember 2009 sei aufzuheben und die Sicherheitsdirektion sei anzuweisen, Y._ eine Niederlassungsbewilligung, eventualiter eine Aufenthaltsbewilligung, auszustellen. Subeventualiter wird beantragt, die Sache sei an die Vorinstanz oder an die Sicherheitsdirektion zurückzuweisen. Gerügt wird die Verletzung von Bundes- und Völkerrecht.
C. Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde, währenddem sich der Regierungsrat und die Sicherheitsdirektion des Kantons Zürich nicht geäussert haben.
D. Mit Verfügung vom 12. Februar 2010 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. Auf die fristgerecht eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten ist einzutreten, da der Ausschlussgrund des <ref-law> nicht greift. Gemäss dem hier noch anwendbaren Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG, BS 1 121; vgl. die Übergangsbestimmung des Art. 126 Abs. 1 AuG [SR 142.20]) hat der Beschwerdeführer 1 grundsätzlich einen Anspruch auf Einbezug seiner Tochter in seine Niederlassungsbewilligung (Art. 17 Abs. 2 Satz 3 ANAG in der Fassung vom 23. März 1990, AS 1991 1034 1043). Die Beschwerdeführer können sich zudem auf das in Art. 8 Ziff. 1 EMRK und <ref-law> garantierte Recht auf Achtung des Familienlebens berufen, da die Beziehung zwischen dem Vater und seiner Tochter offenbar intakt ist. Ob dem Nachzugsanspruch letztlich stattzugeben ist, bildet eine Frage der materiellen Beurteilung (vgl. <ref-ruling> E. 1.1.5 S. 150 mit Hinweisen).
2. 2.1 Die in der Rechtsprechung zu Art. 17 ANAG entwickelten Voraussetzungen für den zeitlich gestaffelten (nachträglichen) Familiennachzug von Kindern unterscheiden sich danach, ob die Gesamtfamilie oder bloss eine Teilfamilie in der Schweiz zusammengeführt werden soll (Nachzug zu den gemeinsamen Eltern oder bloss zu einem getrennt lebenden Elternteil). Anders als bei zusammen lebenden Eltern besteht beim Nachzug zu einem Elternteil kein bedingungsloser Anspruch auf Familienvereinigung. Für eine solche müssen besondere familiäre Gründe bzw. eine zwingend nötig gewordene Änderung in den Betreuungsverhältnissen sprechen (<ref-ruling> E. 2.1 S. 123 mit Hinweisen).
2.2 Die heutige Ehefrau des Beschwerdeführers 1 ist weder die leibliche noch die Adoptivmutter der erwähnten Tochter. Der Beschwerdeführer 1 kann als getrennt lebender Elternteil den nachträglichen Nachzug seiner Tochter demnach nur verlangen, wenn stichhaltige Gründe für deren Übersiedlung in die Schweiz bestehen. Diese Gründe müssen umso gewichtiger sein, je älter die nachzuziehenden Kinder sind (vgl. <ref-ruling> E. 3.1.1 S. 11; <ref-ruling> E. 3.3.2 S. 16).
Die gleichen Grundsätze gelten auch für die Ansprüche aus Art. 8 EMRK und <ref-law>. Diese Bestimmungen, auf die sich der Beschwerdeführer 1 in Bezug auf seine heute noch minderjährige Tochter berufen kann (BGE <ref-ruling> E. 2 S. 13 f.), räumen grundsätzlich nicht jenem Elternteil ein Recht auf Nachzug ein, der freiwillig ins Ausland gezogen ist und ein weniger enges Verhältnis zu den Kindern hat als der Elternteil oder die Verwandten, die für sie in der Heimat sorgen. Der Nachzug der Kinder muss sich zu deren Betreuung aus stichhaltigen Gründen als erforderlich erweisen; dies ist regelmässig nicht der Fall, wenn im Heimatland alternative Pflegemöglichkeiten bestehen, die dem Kindeswohl besser entsprechen, beispielsweise weil dadurch vermieden werden kann, dass die Kinder aus ihrer bisherigen Umgebung und dem ihnen vertrauten Beziehungsnetz gerissen werden (<ref-ruling> E. 2.1 S. 124; <ref-ruling> E. 3.1 S. 10 und E. 5 S. 14 ff., auch mit Hinweis auf das Urteil des Europäischen Gerichtshofes für Menschenrechte [EGMR] Tuquabo-Tekle und andere gegen Niederlande vom 1. Dezember 2005).
3. Das Verwaltungsgericht hat festgestellt, dass für die Beurteilung des Gesuchs auf die Verhältnisse im Zeitpunkt der Einreichung abzustellen sei. Der gegenwärtige, unter Missachtung der Ausreisepflicht herbeigeführte Zustand sei unbeachtlich. Zudem könne die Übertragung des Sorgerechts auf den Beschwerdeführer 1 gemäss zwei Urteilen von libanesischen Scharia-Gerichten wegen Unvereinbarkeit mit dem schweizerischen Ordre public nicht anerkannt werden. Das Verwaltungsgericht verneinte im Ergebnis das Vorliegen von stichhaltigen Gründen, die eine Übersiedlung der Beschwerdeführerin 2 in die Schweiz verlangten.
Die Beschwerdeführer rügen im Wesentlichen die Verletzung des Anspruchs auf Achtung des Privat- und Familienlebens (Art. 8 EMRK und <ref-law>), des Vorrangs des Kindeswohls (Art. 3 KRK), des Anspruchs auf behördliche Beurteilung innert angemessener Frist (<ref-law>), des Anspruchs auf rechtliches Gehör (<ref-law>) sowie des Willkürverbots (<ref-law>).
4. Aufgrund des von der Vorinstanz für das Bundesgericht verbindlich festgestellten Sachverhalts (vgl. <ref-law>) bestanden vorliegend keine zwingenden Gründe für den beantragten Teilfamiliennachzug:
4.1 Die Beschwerdeführerin 2 war zum Zeitpunkt der Einreichung des Gesuches (Ende Oktober 2006) beinahe zehnjährig und hat damit einen wesentlichen Teil ihrer identitätsprägenden Jugend bei ihrer Mutter im Libanon verbracht, wo sie sozial, kulturell und sprachlich integriert war.
Dass die Tochter seit Oktober 2006 beim Vater (zusammen mit dessen neuer Ehefrau) in der Schweiz lebt und sich hier in der Zwischenzeit gut integriert hat, kann grundsätzlich nicht berücksichtigt werden (<ref-ruling> E. 3.3 S. 289). Der Beschwerdeführerin 2 war nur ein kurzfristiger Besuchsaufenthalt bewilligt worden. In der Folge konnte sie nur deshalb in der Schweiz bleiben, weil ihr Aufenthalt während des laufenden Verfahrens geduldet wurde. Eine Änderung der Betreuungsverhältnisse kann jedoch nicht durch Sachumstände belegt werden, welche allein Folge einer vorweggenommenen, eigenmächtigen Verlagerung des Lebensmittelpunktes eines Kindes zum in der Schweiz weilenden Elternteil sind. Die Erforderlichkeit des Nachzugs hat sich vielmehr im Ungenügen der bisherigen Betreuungssituation im Heimatland zu offenbaren, ansonsten die Behörden vor vollendete Tatsachen gestellt werden könnten und der sich rechtskonform verhaltende Bürger benachteiligt würde (<ref-ruling> E. 2.3 S. 255; <ref-ruling> E. 6.3.2 S. 29).
4.1.1 Die Beschwerdeführer beanstanden in diesem Zusammenhang die Verfahrensdauer von mehreren Jahren und berufen sich auf <ref-law>. Sicherlich ist die Verfahrensdauer, insbesondere das zwei Jahre beim Regierungsrat dauernde Rekursverfahren, vorliegend als ausserordentlich lang zu bezeichnen. Dem Verwaltungsgericht selber ist zur Verfahrensdauer aber kein Vorwurf zu machen, hat dieses doch innerhalb von nur etwas mehr als drei Monaten entschieden. Im Übrigen verkennen die Beschwerdeführer, dass eine allfällige Verletzung des Beschleunigungsgebots nicht zu einem absoluten Anspruch auf Familiennachzug führt (Urteil des Bundesgerichts 2C_757/2009 vom 6. Mai 2010 E. 6 mit Hinweis).
4.1.2 Gemäss den verbindlichen Sachverhaltsfeststellungen der Vorinstanz - welche von den Beschwerdeführern nicht als offensichtlich unrichtig im Sinne von <ref-law> gerügt werden - ist davon auszugehen, dass die Beschwerdeführerin 2 seitens ihrer Mutter (allenfalls mit Unterstützung eines Kindermädchens) oder von Verwandten des Beschwerdeführers 1 die altersadäquat notwendige Betreuung in dem ihr vertrauten Umfeld ihres Heimatlandes erhält (bzw. erhalten könnte). Dass die bisherige Betreuung (im Libanon) mit dem Kindeswohl nicht mehr zu vereinbaren ist, wie in der Beschwerde behauptet wird, ist nicht erstellt und lässt sich, wie die Vorinstanz überzeugend ausführt, auch nicht unter Hinweis auf die Einverständniserklärung der Mutter schlüssig belegen. Die Erklärung der Mutter vom 8. Juni 2009, wonach sie zustimme, dass ihre Tochter bei ihrem Vater in der Schweiz bleibe, steht im klaren Gegensatz zu ihren Äusserungen zum Zeitpunkt der Gesuchseinreichung im Herbst 2006 und lässt sich möglicherweise durch eine gewisse Resignation resp. die räumliche Trennung von der Tochter während beinahe vier Jahren erklären. Ohnehin ist für die Beurteilung des Nachzugs auf den Zeitpunkt der Gesuchseinreichung abzustellen (vgl. E. 4.1 hiervor), womit die Erklärung der Mutter nicht entscheidend ins Gewicht fallen kann. Weiter mag es zwar zutreffen, dass die Eltern des Beschwerdeführers 1 zum Zeitpunkt der Gesuchseinreichung gesundheitlich angeschlagen waren und sich dieser Zustand in der Zwischenzeit nicht gebessert hat; inwiefern die Beschwerdeführerin 2 mit Blick auf ihr heutiges Alter nicht mehr sinnvoll betreut werden könnte, ist aber weder ersichtlich noch rechtsgenüglich dargelegt.
4.2 Den Beschwerdeführern gelingt es somit nicht, stichhaltige familiäre Gründe (vgl. E. 2 hiervor) für den beantragten nachträglichen Teilfamiliennachzug darzulegen.
Unter diesen Umständen kann die Frage offen gelassen werden, ob die Vorinstanz den Übergang des Sorgerechts von der Mutter auf den Vater gemäss den Urteilen der libanesischen Scharia-Gerichtsbarkeit zu Recht als offensichtlich unvereinbar mit dem schweizerischen Ordre public im Sinne von Art. 25 lit. c in Verbindung mit <ref-law> (SR 291) bezeichnet hat. Unabhängig davon, ob das Sorgerecht über die Beschwerdeführerin 2 der Mutter oder dem Vater zusteht, bestehen im Heimatland in beiden Fällen genügend Pflegemöglichkeiten, die dem Kindeswohl entsprechen (vgl. E. 4.1.2 hiervor). Zwar mag es zutreffen, dass die Beschwerdeführerin 2 nach beinahe vier Jahren Aufenthalt in der Schweiz - bereits zum zweiten Mal - wieder aus ihrer gewohnten Umgebung gerissen wird. Diese Konstellation hat jedoch einzig der Beschwerdeführer 1 zu verantworten, welcher seine Tochter im Oktober 2006 wider besseres Wissen und entgegen seinen Zusicherungen nach Ablauf des Besuchervisums nicht in ihre Heimat zurückreisen liess. Zudem erhielt er etwa sieben Monate nach der Gesuchseinreichung einen ersten, negativ lautenden Entscheid. Spätestens zu diesem Zeitpunkt musste ihm bewusst werden, dass das Nachzugsbegehren auf ernsthafte Hindernisse stiess, er zumindest mit einer längeren Verfahrensdauer rechnen musste und für seine Tochter geeignete Vorkehren treffen sollte. Mit seinem eigenmächtigen Vorgehen hat letztlich der Beschwerdeführer 1 das Kindeswohl seiner Tochter missachtet; es bleibt unverständlich, warum er sich nicht in der Schweiz um den Familiennachzug bemühte und seine Tochter während des Verfahrens weiter im Libanon wohnen liess, wo sie bestens integriert war und die Schule besuchte.
4.3 Entgegen den Einwänden der Beschwerdeführer verletzt der angefochtene Entscheid unter diesen Umständen weder Art. 8 EMRK bzw. <ref-law> (Achtung des Privat- und Familienlebens) noch die Vorgaben des Übereinkommens vom 20. November 1989 über die Rechte des Kindes (Kinderrechtskonvention, KRK; SR 0.107); aus diesen Bestimmungen - wie auch aus <ref-law> (Schutz der Kinder und Jugendlichen) - ergibt sich kein unmittelbarer Anspruch auf die Erteilung einer ausländerrechtlichen Bewilligung bzw. auf einen entsprechenden - allenfalls auch von den Kindern gewünschten - Familiennachzug zu einem Elternteil, der jahrelang von ihnen getrennt gelebt hat (<ref-ruling> E. 2.2.2 S. 156 f.; <ref-ruling> ff.).
4.4 Soweit die Beschwerdeführer weiter einen Verstoss gegen Art. 29 Abs. 1 und 2 BV (Anspruch auf gleiche und gerechte Behandlung sowie auf rechtliches Gehör) und <ref-law> (Willkürverbot) geltend machen, kann auf die entsprechenden Rügen mangels genügender Begründung nicht eingetreten werden (vgl. <ref-law>; <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen).
4.5 Nach dem Gesagten durfte das Verwaltungsgericht ohne Bundes- oder Völkerrechtsverletzung den Schluss ziehen, die Beschwerdeführer könnten sich nicht auf besondere familiäre Gründe resp. eine wesentliche Veränderung der Betreuungsverhältnisse berufen, welche eine nachträgliche Bewilligung des Familiennachzugs der Tochter zu ihrem in der Schweiz lebenden Vater rechtfertigen würden.
5. 5.1 Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ergebnis besteht auch kein Anlass, dem Eventualantrag (Zurückweisung der Sache an die Vorinstanz zur Neubeurteilung) stattzugeben.
5.2 Bei diesem Verfahrensausgang sind die Gerichtskosten dem unterliegenden Beschwerdeführer 1 aufzuerlegen (<ref-law>). Es ist keine Parteientschädigung geschuldet (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer 1 auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, der Sicherheitsdirektion und dem Regierungsrat des Kantons Zürich, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 9. Juli 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Winiger