Sachverhalt:
A. Die 1929 geborene W._ bezieht Zusatzleistungen zur AHV. Sie ersuchte am 26. September 2006 das Amt für Zusatzleistungen zur AHV/IV der Stadt Zürich um Genehmigung eines Kostenvoranschlags für eine Zahn-Implantatversorgung im Betrag von Fr. 9'439.40. Nachdem die Vertrauensärztin festgestellt hatte, die geplante Behandlung sei zwar zweckmässig, aber nicht einfach und wirtschaftlich, verfügte das Amt am 6. März 2007, der Kostenvoranschlag könne nicht genehmigt werden. W._ erhob dagegen Einsprache, wobei sie zugleich einen zweiten Voranschlag für eine Teilprothese über einen Betrag von Fr. 4'105.20 einreichte und mitteilte, die Implantatversorgung sei bereits durchgeführt worden und habe Fr. 8'846.- gekostet. Das Amt wies die Einsprache am 12. Juli 2007 in Bezug auf die Kosten für die Implantatversorgung ab, ohne sich zum Anspruch auf Vergütung der Kosten für die Prothese zu äussern. Der Bezirksrat Zürich wies mit Beschluss vom 17. Januar 2008 die Einsprache in Bezug auf die Kostenübernahme für das Implantat ab, ebenso den eventualiter gestellten Antrag auf Übernahme der Kosten für die Teilprothese im Betrag von Fr. 4'105.20.
B. Das Sozialversicherungsgericht des Kantons Zürich hiess die dagegen erhobene Beschwerde mit Entscheid vom 4. November 2009 in dem Sinne teilweise gut, als es den angefochtenen Beschluss insoweit aufhob, als damit der Anspruch auf Vergütung der Kosten im Betrag von Fr. 4'105.20 abgewiesen wurde, und es die Sache an das Amt für Zusatzleistungen zurückwies, damit dieses im Sinne der Erwägungen über den Anspruch neu befinde.
C. Das Amt für Zusatzleistungen der Stadt Zürich erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, der Anspruch auf Vergütung der Teilprothesenversorgung sei abzuweisen.
W._ und das Bundesamt für Sozialversicherungen (BSV) verzichten auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) ist zulässig gegen Entscheide, die das Verfahren abschliessen (<ref-law>) sowie gegen selbstständig eröffnete Vor- und Zwischenentscheide über die Zuständigkeit und über Ausstandsbegehren (<ref-law>). Gegen andere selbstständig eröffnete Vor- und Zwischenentscheide ist die Beschwerde nach <ref-law> zulässig, sofern - alternativ - der Entscheid einen nicht wieder gutzumachenden Nachteil bewirken kann (Abs. 1 lit. a) oder die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (Abs. 1 lit. b).
1.2 Beim vorinstanzlichen Entscheid, mit welchem das beschwerdeführende Amt verpflichtet wird, die Voraussetzungen der Einfachheit, Zweckmässigkeit und Wirtschaftlichkeit der Teilprothesenversorgung zu prüfen, handelt es sich um einen Rückweisungsentscheid und damit nach der Terminologie des BGG um einen Zwischenentscheid (<ref-ruling> E. 4.2 S. 481; Urteil 8C_125/2008 vom 13. Oktober 2008; vgl. auch Hansjörg Seiler, Rückweisungsentscheide in der neueren Sozialversicherungspraxis des Bundesgerichts, in: Schaffhauser/ Schlauri [Hrsg.], Sozialversicherungsrechtstagung 2008, 2009, S. 29). Er kann daher nur unter den Voraussetzungen von <ref-law> selbstständig angefochten werden. Dabei liegt ein nicht wieder gutzumachender Nachteil vor, wenn eine Behörde durch die Rückweisung gezwungen wird, entgegen ihrer Auffassung eine neue Anordnung zu erlassen (<ref-ruling> E. 5.2 S. 483 ff.; SVR 2008 IV Nr. 31 S. 100 E. 1.2, I 126/07). So verhält es sich hier. Die vorinstanzlich angeordnete Prüfung der Voraussetzungen für die Kostenübernahme der Teilprothesenversorgung ist nach Ansicht des beschwerdeführenden Amtes falsch, weil die Voraussetzungen für die Anwendung der Austauschbefugnis nicht gegeben sind. Auf die Beschwerde ist daher einzutreten.
2. 2.1 Streitig ist die Kostenübernahme für eine Zahnbehandlung, die vor Inkrafttreten des neuen ELG am 1. Januar 2008 (AS 2007 6055) erfolgt ist. Entsprechend den allgemeinen intertemporalrechtlichen Grundsätzen richtet sich die Beurteilung daher noch nach den Vorschriften des bis Ende 2007 in Kraft gewesenen aELG. Ebenfalls noch anwendbar ist die (per Ende 2007 aufgehobene) ELKV.
2.2 Nach Art. 3d Abs. 1 lit. a aELG haben die Bezüger einer jährlichen Ergänzungsleistung Anspruch auf die Vergütung von ausgewiesenen, im laufenden Jahr entstandenen Kosten für Zahnarzt. Der Bundesrat bezeichnet die Kosten, die nach Abs. 1 vergütet werden können (Abs. 4). Er hat diese Zuständigkeit an das EDI delegiert (Art. 19 Abs. 1 ELV). Gemäss Art. 8 Abs. 1 ELKV werden unter Vorbehalt von Abs. 3 Kosten für einfache, wirtschaftliche und zweckmässige Zahnbehandlungen vergütet. Nach Abs. 3 werden höchstens Fr. 3'000.- vergütet, wenn die Behandlung ohne vorgängig eingereichten und genehmigten Kostenvoranschlag durchgeführt wurde. Nach der Rechtsprechung handelt es sich dabei um eine Ordnungsvorschrift, die nicht ausschliesst, dass auch ohne genehmigten Voranschlag höhere Kosten vergütet werden, wenn nachgewiesen werden kann, dass eine einfache, wirtschaftliche und zweckmässige Behandlung mehr kostet (<ref-ruling> E. 5.3 und 5.4).
3. 3.1 Die Vorinstanz hat erwogen, die Beschwerdegegnerin habe keinen Anspruch auf Vergütung der durchgeführten Implantatversorgung, da diese nicht einfach und wirtschaftlich sei. Hingegen hätte sie unter dem Titel der Austauschbefugnis Anspruch auf Vergütung der Teilprothesenversorgung, sofern diese die Voraussetzungen der Einfachheit, Zweckmässigkeit und Wirtschaftlichkeit erfülle; das sei bisher nicht abgeklärt worden und noch zu prüfen.
3.2 Sachverhaltlich ist unbestritten, dass die Beschwerdegegnerin die teurere Implantatversorgung anstelle einer wirtschaftlicheren Teilprothese durchführen liess. Rechtlich ist sodann nicht mehr bestritten, dass sie keinen Anspruch auf Vergütung der Kosten für diese Implantatversorgung hat. Das beschwerdeführende Amt bestreitet nicht, dass die Beschwerdegegnerin grundsätzlich Anspruch auf die Kostenübernahme für die Teilprothese hätte. Es stellt auch nicht in Frage, dass, wie die Vorinstanz gestützt auf <ref-ruling> erkannt hat, der Umstand, dass ein genehmigter Kostenvoranschlag vor der Behandlung nicht vorlag, nicht grundsätzlich die Vergütung ausschliesst. Streitig und zu prüfen ist jedoch die von der Vorinstanz bejahte Anwendung der Austauschbefugnis.
4. 4.1 Die aus dem Verhältnismässigkeitsprinzip fliessende Rechtsfigur der Austauschbefugnis wurde ursprünglich in den invalidenversicherungsrechtlichen Bereichen der Hilfsmittelversorgung (<ref-law>) und der medizinischen Massnahmen (<ref-law>) entwickelt. Im Bereich der Hilfsmittel ist sie in <ref-law> ausdrücklich verankert worden. Sie wurde aber von der Rechtsprechung auch in weiteren Bereichen zur Anwendung gebracht, wo sie positivrechtlich nicht ausdrücklich vorgesehen ist, so in Bezug auf die Hilfsmittel der AHV (<ref-ruling>, E. 3.4.3), in der Krankenversicherung (Urteil K 95/03 vom 11. Mai 2004, E. 4) sowie in der Arbeitslosenversicherung (Urteil C 241/03 vom 3. Mai 2004, E. 3). Die Rechtsprechung hat allerdings betont, dass die Austauschbefugnis nicht einen im gesamten Sozialversicherungsrecht anwendbaren Grundsatz darstelle; ihrer Anwendung kann die durch Auslegung zu ermittelnde ratio legis entgegenstehen (<ref-ruling> E. 3.2.3 S. 112). Die gesetzliche Zielsetzung kann aber auch gerade für die Anwendbarkeit der Austauschbefugnis sprechen (<ref-ruling> E. 3.4.4 in Bezug auf die Hilfsmittel der AHV, die den gleichen Zweck verfolgen wie diejenigen der IV), ebenso der Umstand, dass dadurch keine finanzielle Mehrbelastung der Sozialversicherung verbunden ist (<ref-ruling> E. 3.4.5).
4.2 Soweit die Austauschbefugnis überhaupt anwendbar ist, ist sie an folgende Voraussetzungen gebunden: Erstens muss ein substitutionsfähiger aktueller gesetzlicher Anspruch vorliegen. Zweitens muss die beantragte bzw. effektiv angeschaffte Leistung auf weitere Sicht funktionell gleichartig sein wie diejenige, auf welche ein Anspruch bestünde; ist sie teurer, so besteht Anspruch auf die Vergütung im Umfang der Kosten der (günstigeren) Leistung, auf die ein Anspruch bestünde (<ref-ruling> E. 3.2.3 S. 112 f., 127 V 121 E. 2b S. 124).
4.3 Nach der vor allem in der Krankenversicherung geltenden Rechtsprechung kann die Austauschbefugnis nicht dazu führen, dass Pflichtleistungen durch Nichtpflichtleistungen ersetzt werden, auch wenn diese weniger kostspielig wären (<ref-ruling> E. 4.3, 131 V 107 E. 3.2.2). Der Grund dafür liegt vor allem in der besonderen gesetzlichen Regelung der Leistungsansprüche in der obligatorischen Krankenpflegeversicherung: Das Prinzip der Inlandbehandlung ist eng verbunden mit dem gesetzlichen System der Spitalplanung und -finanzierung, das durch eine freie Wahl zwischen In- und Auslandbehandlung in Frage gestellt würde (<ref-ruling> E. 3.2 S. 276). Sodann besteht in der Krankenversicherung ein besonderes System der zugelassenen Leistungserbringer (<ref-law>), weshalb nicht unter Berufung auf die Austauschbefugnis eine von einem nicht zugelassenen Leistungserbringer erbrachte Leistung übernommen werden kann (<ref-ruling> E. 1b; Urteil K 67/02 vom 30. Juli 2003, E. 3). Schliesslich können auch die positivlistenpflichtigen Leistungen nicht unter Berufung auf die Austauschbefugnis durch andere substituiert werden (Urteil K 63/02 vom 1. September 2003, E. 3.3).
4.4 Demgegenüber wurden im Bereich der medizinischen Massnahmen nach <ref-law> im Rahmen der Austauschbefugnis die Kosten im Umfang der Kosten einer gemäss herkömmlicher Methode durchgeführten Skolioseoperation übernommen, nachdem eine wissenschaftlich nicht anerkannte, teurere Operation durchgeführt worden war (Urteil 9C_13/2009 vom 6. Oktober 2009, E. 7.2). In Bezug auf die Hilfsmittel der Invalidenversicherung besteht sodann - obwohl die Liste der Hilfsmittel grundsätzlich abschliessend ist - Anspruch auf ein nicht auf der Liste aufgeführtes Mittel, sofern dieses günstiger ist als ein dem Versicherten zustehendes, auf der Liste aufgeführtes Mittel (<ref-law>; vgl. Urteil I 684/06 vom 12. Februar 2007, E. 6). Ebenso gilt als Anwendungsfall der Austauschbefugnis, dass ein obligatorisch Krankenpflegeversicherter auch bei stationärer Behandlung in der Privat- oder Halbprivatabteilung eines Spitals Anspruch auf diejenige Vergütung seitens der obligatorischen Krankenpflegeversicherung hat, die bei Aufenthalt in der allgemeinen Abteilung geschuldet gewesen wäre (<ref-ruling> E. 3c S. 351).
4.5 Im Rahmen der Ergänzungsleistungen hat die Rechtsprechung erkannt, dass die Vergütung der Kostenbeteiligungen nach <ref-law> (Art. 14 Abs. 1 lit. g ELG bzw. Art. 3d Abs. 1 lit. f aELG) nur in Bezug auf Leistungen gilt, die Pflichtleistungen im Sinne des KVG sind, weshalb insoweit eine Austauschbefugnis nicht zum Tragen kommt (Urteil P 9/02 vom 2. Juli 2002 E. 3a; vgl. auch BGE 123 V252 E. 2c S. 256 f.; RALPH JÖHL, Ergänzungsleistungen zur AHV/IV, in: Ulrich Meyer [Hrsg.] Schweizerisches Bundesverwaltungsrecht [SBVR], Band XIIII, Soziale Sicherheit, 2. Aufl., Basel 2007 S. 1871). Deshalb wurde auch die Anwendbarkeit der Austauschbefugnis verneint in Bezug auf eine Behandlung im Ausland, da die einschränkende Umschreibung der Kostenübernahme für Behandlungen im Ausland in Art. 5 Abs. 2 ELKV mit der Rechtslage in der Krankenversicherung übereinstimmt (Urteil P 18/05 vom 20. Juli 2005 E. 3.4). Diese Rechtsprechung gründet somit darauf, dass die Kostenübernahme durch die EL für die Krankheitskosten gemäss Art. 3d Abs. 1 lit. f aELG auf die Regelung des KVG abstellt, so dass auch die dort geltenden Einschränkungen der Austauschbefugnis (E. 4.3) konsequenterweise gleichermassen gelten müssen.
4.6 In Bezug auf die Zahnbehandlungskosten gemäss Art. 3d Abs. 1 lit. a aELG (bzw. Art. 14 Abs. 1 lit. a ELG) verhält es sich anders: Es handelt sich dabei um diejenigen Zahnarztkosten, die nicht gemäss <ref-law> durch die Krankenversicherung übernommen werden; dafür besteht weder in Art. 3d Abs. 1 lit. a ELG noch in der ELKV ein abschliessender Katalog von Massnahmen oder ein Ausschluss bestimmter Massnahmen (<ref-ruling> E. 4.3.4). Die Zahnarztbehandlungen sind - anders als die dem KVG unterstehenden ärztlichen Behandlungen - grundsätzlich nicht sozialversicherungsrechtlich reglementiert. Die Gründe, die im Bereich der Krankenversicherung für eine Einschränkung der Austauschbefugnis sprechen, liegen somit hier nicht vor.
4.7 Die Ergänzungsleistungen werden ausgerichtet, um den Berechtigten den Existenzbedarf zu decken (<ref-law>). Aus dieser Zwecksetzung lässt sich ebenfalls nicht ableiten, der Begriff der Kosten für den Zahnarzt sei einschränkend auszulegen (<ref-ruling> E. 4.3.). Schliesslich entsteht durch die Anwendung der Austauschbefugnis auch keine finanzielle Mehrbelastung für die EL; denn entgegen den Befürchtungen in der Beschwerde wird selbstverständlich die EL nicht allfällige Folgekosten der Implantatversorgung zu übernehmen haben, soweit diese höher sein werden als diejenigen einer einfachen und wirtschaftlichen Ausführung. In der Lehre wird denn auch die Austauschbefugnis für Zahnbehandlungskosten in der EL bejaht (Jöhl, a.a.O., S. 1872 Rz. 330 f.). Das Eidg. Versicherungsgericht hat im Urteil P 10/00 vom 6. Juli 2001 zur Einholung eines Gutachtens und neuer Verfügung "allenfalls auch unter dem Blickwinkel der Austauschbefugnis" zurückgewiesen. Diese dort implizit und ohne nähere Begründung bejahte Anwendung der Austauschbefugnis ist nach dem Gesagten zu bestätigen. Zu prüfen sind die einzelnen Voraussetzungen.
5. Das Beschwerde führende Amt verneint den Anspruch, weil kein gesetzlicher Anspruch auf die Implantatversorgung bestehe und mithin kein substitutionsfähiger Anspruch vorliege. Damit verkennt es die Funktion dieses Erfordernisses: Der gesetzliche Anspruch muss nicht auf die (angeschaffte) teurere Leistung bestehen, sondern auf die (günstigere), welche durch die angeschaffte Leistung substituiert wurde (Urteile I 684/06 vom 12. Februar 2007, E. 6.3, und I 736/04 vom 21. März 2006, E. 2.5), vorliegend also nicht auf die Implantatversorgung, sondern auf die Teilprothese.
6. 6.1 Funktionelle Gleichartigkeit liegt vor, wenn die angeschaffte (teurere) Leistung (auch) die Funktionen übernimmt, welche die zustehende günstigere Leistung übernommen hätte (<ref-ruling> E. 3.2.1 und 3.2.3); wenn sie daneben noch weitere Funktionen wahrnimmt, welche die günstigere Leistung nicht übernehmen könnte, so schadet dies nicht (vgl. z.B. <ref-ruling>.2 in Bezug auf das Verhältnis zwischen dem Rollstuhl ohne motorischen Antrieb, auf welchen Anspruch bestand, und dem angeschafften motorisierten Rollstuhl; Urteil I 684/06 vom 12. Februar 2007 E. 6.2 in Bezug auf das Verhältnis zwischen einem zugesprochenen Elektromobil und einem angeschafften Motorfahrzeug; Urteil I 736/04 vom 21. März 2006 E. 2.5 in Bezug auf einen Anbau, der nebst den Funktionen des zugesprochenen Treppenlifts auch weitere Funktionen übernimmt). Verneint wird die Anwendung der Austauschbefugnis, wenn ein Mittel angeschafft wird, das auch ohne die gesundheitliche Beeinträchtigung angeschafft worden wäre (Urteil I 521/05 vom 25. November 2005 E. 2.2 bzgl. Melkanlage).
6.2 Im Lichte dieser Grundsätze kann die funktionelle Gleichartigkeit der beiden in Frage stehenden Behandlungsvarianten nicht verneint werden: Wie das Beschwerde führende Amt selber vorbringt, führen beide dazu, dass man wieder kauen kann. Die teurere Implantatversorgung ist eine luxuriösere Variante und mag zusätzlich zur Ermöglichung der Kaufunktion weitere Funktionen und Vorteile haben. Das schliesst aber nach dem Gesagten die funktionelle Gleichartigkeit nicht aus, da sie jedenfalls auch die Funktion wahrnimmt, welche die Teilprothese wahrgenommen hätte.
6.3 Wenn die Austauschbefugnis auf dem Verordnungsweg näher präzisiert und pauschaliert wird, besteht kein weitergehender Anspruch, so wenn in Ziff. 14.05 Anhang HVI die Kostenbeteiligung bei einem anstelle eines Treppenfahrstuhls angeschafften Treppenlift auf Fr. 8'000.- unter Ausschluss von Reparaturkosten begrenzt wird (Urteil 9C_828/2008 vom 25. Februar 2009, E. 4.2.3). Solche Regelungen bestehen hier aber nicht.
7. Das Beschwerde führende Amt verneint schützenswerte Gründe, welche zur Anwendung der Austauschbefugnis führen könnten. Es beruft sich dabei auf <ref-ruling> E. 4b und 131 V 107 E. 3.2.1. In <ref-ruling> E. 4b wurde zusätzlich zum Erfordernis der zu substituierenden gesetzlichen Leistung geprüft (und bejaht), ob schützenswerte Gründe für eine Zulassung der Austauschbefugnis vorliegen. In <ref-ruling> E. 3.2.1 S. 111 wurde ausgeführt, Austauschbefugnis bedeute, dass die versicherte Person zu entschädigen sei, wenn sie aus schützenswerten Gründen von einem gesetzlichen Leistungsanspruch keinen Gebrauch macht und stattdessen einen funktionell gleichen Behelf zur Erreichung desselben gesetzlichen Ziels wählt. Damit ist jedoch nicht gemeint, dass als selbstständiges zusätzliches Kriterium im Einzelfall geprüft werden müsste, ob ein schutzwürdiges Interesse vorliege. Sofern in einem Bereich aufgrund der Auslegung des Gesetzes überhaupt die Austauschbefugnis bejaht wird, deckt sich das Kriterium der schützenswerten Gründe mit demjenigen der funktionellen Gleichartigkeit, weil es grundsätzlich ohne Bedeutung ist, auf welchem Weg oder durch welches Mittel das gesetzliche Ziel angestrebt wird (vgl. <ref-ruling> E. 3.2.1; Urteil H 199/01 E. 2.3.1).
8. Das Beschwerde führende Amt verneint schliesslich die Anwendbarkeit der Austauschbefugnis mit dem Hinweis, die gesetzliche Lösung führe nicht zu einem krass unbefriedigenden Ergebnis. In der Rechtsprechung wurde indessen die Anwendung der Austauschbefugnis nicht an das Erfordernis geknüpft, dass andernfalls ein krass unbefriedigendes Ergebnis resultieren würde. Es besteht kein Anlass, über die genannten Voraussetzungen hinaus dieses Erfordernis aufzustellen; denn die Anwendung der Austauschbefugnis führt ja nicht dazu, dass sich in finanzieller Hinsicht eine teurere als die gesetzliche Lösung ergäbe. Vielmehr würde die Verneinung der Austauschbefugnis dazu führen, dass nicht einmal die Leistungen erbracht würden, die der gesetzlichen Lösung entsprechen. Unerheblich ist deshalb auch der Hinweis des beschwerdeführenden Amtes, die EL-Bezüger sollten nicht besser gestellt werden als die Selbstzahler, die sich zum grössten Teil keine Implantatversorgung leisten könnten; denn auch der Beschwerdegegnerin werden aufgrund des angefochtenen Urteils richtigerweise nicht die Kosten der Implantatversorgung vergütet, sondern nur (allenfalls) die Kosten einer Teilprothese. Aus dem gleichen Grund ist der angefochtene Entscheid entgegen den Vorbringen in der Beschwerde auch nicht unverhältnismässig: Es wird nicht eine teurere Luxusversorgung finanziert, sondern nur eine einfache und wirtschaftliche, auf welche Anspruch besteht.
9. Dem Ausgang des Verfahrens entsprechend hat das beschwerdeführende Amt die Gerichtskosten zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden dem beschwerdeführenden Amt auferlegt.
3. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich, dem Bundesamt für Sozialversicherungen und dem Bezirksrat Zürich schriftlich mitgeteilt.
Luzern, 7. April 2010
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Helfenstein Franke