Sachverhalt: A. Die 1942 geborene R._ bezieht seit 1. Januar 2006 eine Altersrente für langjährig Versicherte der Deutschen Rentenversicherung Bund, Berlin (Rentenbescheid vom 9. Februar 2006). Die Durchführungsstelle Zusatzleistungen AHV/IV der Gemeinde Y._ (im Folgenden: Durchführungsstelle) verfügte am 17. Januar 2007 die Zusprechung von Ergänzungsleistungen ab 1. November 2006. Der Ehemann von R._, X._, geboren 1943, bezieht seit 1. Februar 2007 ebenfalls eine Altersrente, weshalb die Durchführungsstelle mit Verfügung vom 27. März 2007 die Ergänzungsleistungen ab 1. Februar 2007 neu festsetzte. Bereits mit Schreiben vom 26. Februar 2007 hatte R._ unter anderem eine Rechnung betreffend eine (am 21. Juni 2006 begonnene) Zahnbehandlung ihres Ehemannes bei Dr. med. dent. H._, Deutschland, eingereicht und um Übernahme der entsprechenden Kosten ersucht. Am 28. Februar 2007 informierte die Durchführungsstelle, von den Zahnarztkosten könne durch die Zusatzleistungen zur AHV/IV nichts übernommen werden und erliess am 27. Juli 2007 eine entsprechende Verfügung. Nachdem R._ und X._ hiegegen Einsprache erhoben hatten, forderte die Durchführungsstelle das Ehepaar R._ am 10. September 2007 auf, das Formular "Zahnschäden gemäss KVG Befunde/Kostenvoranschlag" vom behandelnden Zahnarzt ausfüllen zu lassen. Gleichzeitig wies sie darauf hin, dass die Einsprache nicht weiterbehandelt werden könne, bevor das Formular eingereicht worden sei. Mit einer weiteren Verfügung vom 12. September 2007 passte die Durchführungsstelle die EL-Leistungen ab 1. Oktober 2007 unter Hinweis auf den veränderten Umrechnungskurs zwischen Euro und Schweizer Franken an. Am 16. Oktober 2007 führten R._ und X._ aus, ein Behandlungsplan des Dr. med. dent. H._ vom 23. Juni 2006 sei der Durchführungsstelle seit 10. November 2006 bekannt. Das einverlangte Formular reichten sie nicht ein, legten indes eine Behandlungsbestätigung des Dr. med. dent. H._ (vom 11. Oktober 2007) und zwei Rechnungen (vom 8. Februar und 30. März 2007) vor. Mit Entscheid vom 19. Oktober 2007 wies die Durchführungsstelle die Einsprache von R._ und X._ gegen die Verfügung vom 12. September 2007 (Anpassung der EL-Leistungen) ab. Nachdem der von ihr angefragte Vertrauenszahnarzt Dr. med. dent. J._ (Schweiz) am 21. Oktober 2007 mitgeteilt hatte, er sei aufgrund der vorhandenen Akten nicht in der Lage, die Behandlung des Dr. med. dent. H._ zu beurteilen, bestätigte die Durchführungsstelle die Ablehnung der Kostenübernahme für die Zahnbehandlung (Einspracheentscheid vom 30. Oktober 2007). Der Bezirksrat Z._, bei welchem R._ und X._ (unter anderem) gegen die Einspracheentscheide betreffend Anpassung der EL (vom 19. Oktober 2007) und Nichtübernahme der Kosten für die Zahnbehandlung in Deutschland (vom 30. Oktober 2007) Beschwerde erhoben hatten, vereinigte (u.a.) diese Verfahren und wies die Einsprachen mit Beschluss vom 14. Januar 2008 ab. B. Die hiegegen erhobene Beschwerde von R._ und X._ wies das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 26. Dezember 2008 ab. C. R._ und X._ lassen Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit folgendem Rechtsbegehren: "Das Urteil des Sozialversicherungsgerichts des Kantons Zürich vom 26. Dezember 2008 und der Beschluss des Bezirksrats Z._ vom 14. Januar 2008 seien teilweise aufzuheben, die Einspracheentscheide der Gemeindeverwaltung Y._ vom 19. Oktober 2007 und 30. Oktober 2007 seien vollständig aufzuheben, und den Beschwerdeführern seien die ab 1. November 2006 entstandenen Kosten für die zahnärztliche Behandlung zuzusprechen. Im Übrigen sei festzustellen, dass die Ergänzungsleistungen ab 1. Oktober 2007 nicht neu zu berechnen sind, eventualiter nur unter Berücksichtigung eines erhöhten Renteneinkommens von Fr. 71.17." Gleichzeitig ersuchen die Beschwerdeführer um Gewährung der unentgeltlichen Prozessführung und Verbeiständung. Die Durchführungsstelle schliesst auf Abweisung der Beschwerde. Vorinstanz und Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung. 