Faits:
A. Par arrêté du 22 juillet 2009, le Conseil d'Etat du canton de Genève (ci-après: le Conseil d'Etat) a constaté l'aboutissement de l'initiative populaire municipale intitulée "Sauvons nos parcs au bord du lac" (ci-après: l'initiative ou l'IN-3) dont la teneur est la suivante:
"Aucune construction nouvelle ne doit être érigée sur le domaine public ou privé de la Ville de Genève entre les bords du lac d'une part, et le quai Général-Guisan, le quai Gustave-Ador, le quai du Mont-Blanc, le quai Wilson et la rue de Lausanne y compris, d'autre part. Il en est de même pour les parcs de la Grange, des Eaux-Vives, de la partie sud du Palais des Nations et pour le Jardin botanique, sous réserve de constructions modestes indispensables à l'exploitation de ces jardins.
La Ville de Genève s'oppose à toute modification des zones de verdure et à toute nouvelle construction dans tous les parcs et les quais situés dans le périmètre défini ci-dessus, qui fait l'objet d'un plan annexé au règlement. Aucune extension des rives du lac ne doit être réalisée, sous réserve d'aménagements modestes, ni aucune installation permettant d'accéder depuis les berges à de nouvelles constructions érigées sur le lit du lac. Des pavillons provisoires, tels que stands de glaces, billetterie, WC, aménagements pour les spectacles peuvent être réalisés par un arrêté du Conseil municipal. Le Conseil administratif est chargé de présenter une proposition documentée portant sur le site de la rade, en vue de son inscription au patrimoine mondial de l'Unesco".
B. Le Conseil administratif de la Ville de Genève (ci-après: le Conseil administratif) n'a pas déposé le rapport sur la validité et la prise en considération de l'IN-3 dans le délai de trois mois prévu à l'art. 36A de la loi sur l'administration des communes du 13 avril 1984 (LAC; RSG B 6 05). Le Conseil municipal ne s'est pas prononcé sur la validité de l'initiative dans le délai de neuf mois prévu à l'art. 36B LAC, soit au plus tard le 22 avril 2010.
Le Conseil administratif a déposé son rapport au Conseil municipal en date du 14 septembre 2010. Il a considéré que l'initiative comportait un objectif disproportionné et était politiquement inopportune. Il a conclu au rejet de l'initiative. Vu l'écoulement du délai de neuf mois prévu à l'art. 36B al. 5 LAC, le Conseil municipal a informé le Service de surveillance des communes de la validation de l'IN-3 par le biais d'une décision automatique, le 21 septembre 2010.
Par arrêté du 22 décembre 2010, publié dans la Feuille d'avis officielle du canton de Genève le 27 décembre 2010, le Conseil d'Etat, statuant en tant qu'autorité de surveillance des communes, a annulé la décision automatique précitée et invalidé partiellement l'IN-3 en scindant son contenu en cinq invites, dont deux sont annulées et une déclarée invalide. Le motif d'invalidation réside dans la non-conformité du contenu de l'initiative au droit supérieur (absence de compétence des autorités municipales pour les objets concernés).
C. Par arrêt du 30 juillet 2012, la Chambre administrative de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a rejeté le recours formé notamment par A._ et B._ contre l'arrêté du 22 décembre 2010 du Conseil d'Etat. Elle a considéré en substance que le Conseil d'Etat pouvait prononcer en tout temps l'annulation des délibérations du Conseil municipal prises en violation des lois et règlements en vigueur (art. 67 let. b LAC) et que, par conséquent, l'exécutif cantonal était compétent pour annuler la décision de validation de l'initiative prise par le Conseil municipal dans l'exercice de ses fonctions délibératives (art. 30 al. 1 let. y LAC). Elle a ensuite examiné chacune des invites encore litigieuses pour retenir que les objets concernés ne relevaient pas de la compétence communale.
D. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent principalement au Tribunal fédéral d'annuler l'arrêt cantonal et l'arrêté du Conseil d'Etat du 27 décembre 2010. Ils concluent subsidiairement au renvoi de la cause au Conseil d'Etat pour que le Conseil municipal puisse mener la procédure de l'initiative IN-3 en application de la procédure des art. 68A à 69 Cst/GE.
La Cour de justice s'en rapporte à justice quant à la recevabilité du recours et persiste dans les considérants et le dispositif de son arrêt. Le Conseil administratif s'en rapporte à justice. Le Conseil d'Etat conclut, à la forme, à l'irrecevabilité du recours et, au fond, à son rejet. Les recourants ont répliqué par courrier du 3 décembre 2012.

Considérant en droit:
1. Selon l'art. 82 let. c LTF, le Tribunal fédéral connaît des recours qui concernent le droit de vote des citoyens ainsi que les élections et votations populaires.
1.1 Cette disposition reprend la règle de l'art. 85 let. a OJ et permet de recourir contre l'ensemble des actes affectant les droits politiques (cf. Message concernant la révision totale de l'organisation judiciaire fédérale du 28 février 2001, FF 2001 4118). Le recours en matière de droits politiques permet en particulier au citoyen de se plaindre de ce qu'une initiative populaire a été indûment soustraite au scrutin populaire, parce qu'elle a été déclarée totalement ou partiellement invalide par l'autorité chargée de cet examen (<ref-ruling> consid. 1.1 p. 193; cf. <ref-ruling> consid. 1 p. 175 s.).
1.2 La qualité pour recourir dans le domaine des droits politiques appartient à toute personne disposant du droit de vote dans l'affaire en cause (<ref-law>), même si elle n'a aucun intérêt juridique personnel à l'annulation de l'acte attaqué (<ref-ruling> consid. 1 p. 292). La qualité pour agir des deux citoyens de la Ville de Genève est ainsi indiscutable.
2. Les recourants critiquent d'abord l'intervention du Conseil d'Etat en tant qu'autorité de surveillance des communes. Sans se plaindre d'arbitraire, ils affirment que les délais prévus à l'art. 68 E Cst./GE sont impératifs et que le Conseil d'Etat n'était pas compétent pour invalider l'initiative. Les intéressés font ensuite valoir que l'initiative litigieuse est conforme au droit supérieur.
2.1 Saisi d'un recours pour violation des droits politiques, le Tribunal fédéral revoit librement l'interprétation et l'application du droit fédéral et du droit constitutionnel cantonal, ainsi que des dispositions de rang inférieur qui sont étroitement liées au droit de vote ou en précisent le contenu et l'étendue (<ref-ruling> consid. 1.3 p. 284; <ref-ruling> consid. 2 p. 190).
Le Tribunal fédéral n'examine en revanche que sous l'angle restreint de l'arbitraire l'interprétation des autres règles du droit cantonal, en particulier les dispositions de procédure (<ref-ruling> consid. 4 p. 131 et les arrêts cités). Les dispositions de la LAC qui déterminent l'étendue du pouvoir de surveillance du Conseil d'Etat, sont sans incidence directe sur le contenu et l'étendue du droit de vote proprement dit. Elles s'apparentent à des dispositions d'exécution et de procédure, telles qu'elles sont réservées aux art. 68E al. 1 et 69 Cst./GE. Le pouvoir d'examen du Tribunal fédéral est dès lors limité à l'arbitraire (arrêt 1C_49/2010 du 8 juillet 2010 consid. 3.1). En présence de deux interprétations également défendables, le Tribunal fédéral s'en tient en général à celle retenue par la plus haute autorité cantonale (<ref-ruling> consid. 4 p. 131 et les arrêts cités).
2.2 En vertu de l'<ref-law>, les mémoires de recours doivent être motivés. Selon l'<ref-law>, les motifs doivent exposer succinctement en quoi l'acte attaqué viole le droit. Pour satisfaire à cette exigence, il appartient au recourant de discuter au moins brièvement les considérants de la décision litigieuse (<ref-ruling> consid. 2.1 p. 245). En particulier, la motivation doit se rapporter à l'objet du litige tel qu'il est circonscrit par la décision attaquée (<ref-ruling> consid. 6.4 p. 121).
Les griefs de violation des droits fondamentaux et des dispositions de droit cantonal - non liées au droit de vote - sont en outre soumis à des exigences de motivation accrues (<ref-law>). La partie recourante doit alors mentionner les principes constitutionnels qui n'auraient pas été respectés et expliquer de manière claire et précise en quoi ces principes auraient été violés; de même, elle doit citer les dispositions du droit cantonal dont elle se prévaut et démontrer de manière suffisamment motivée en quoi ces dispositions auraient été appliquées arbitrairement ou d'une autre manière contraire au droit (<ref-ruling> consid. 2.8 p. 494). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 4.2.3 p. 5).
2.3 En l'espèce, les recourants ne discutent pas l'argumentation retenue par la cour cantonale. Ils se contentent de disserter, de manière confuse, sur les éléments retenus par le Conseil d'Etat dans son arrêté du 22 décembre 2010. Le caractère appellatoire du recours se constate notamment, dans le mémoire des recourants au Tribunal fédéral, par les reprises mot à mot de paragraphes entiers du texte de leur mémoire de recours devant la cour cantonale. Le recours s'apparente ainsi à une diatribe dirigée contre l'autorité politique, alors que le recours cantonal a un effet dévolutif complet (art. 67 al. 1 loi genevoise du 12 septembre 1985 sur la procédure administrative [LPA/GE; RS/GE E 5 10]), de sorte que seule la décision de l'autorité judiciaire fait l'objet de la procédure de recours devant le Tribunal fédéral. Pour preuve, les intéressés n'indiquent nulle part en quoi l'arrêt attaqué serait contraire au droit. Ils s'en prennent toujours et seulement à l'arrêté du Conseil d'Etat. Les recourants, pourtant assistés d'un mandataire professionnel, désignent d'ailleurs faussement l'objet du recours devant le Tribunal de céans comme étant "l'arrêté du Conseil d'Etat".
En particulier, les recourants ne critiquent pas l'argumentation - fondée sur les art. 67 let. b et 30 al. 1 let. y LAC - de l'instance précédente tendant à démontrer que le Conseil d'Etat était compétent pour annuler la décision de validation de l'initiative prise par le Conseil municipal dans l'exercice de ses fonctions délibératives. Comme s'ils plaidaient devant une cour d'appel, ils se contentent d'affirmer que les délais prévus à l'art. 68E Cst./GE sont impératifs, de sorte que "les autorités de la Ville de Genève ne peuvent plus traiter de l'invalidation de l'initiative litigieuse, ni modifier son contenu", sans démontrer concrètement et précisément en quoi et pour quel motif l'appréciation de la cour cantonale serait insoutenable. Il n'appartient pas au Tribunal fédéral d'examiner d'office ce qu'il en est (<ref-ruling> consid. 1.4.2 p. 254), ce d'autant moins que son pouvoir d'examen est limité à l'arbitraire sur cette question (cf. supra consid. 2.1). Faute de motivation satisfaisant aux exigences de l'<ref-law>, le grief doit être déclaré irrecevable.
Quant à l'examen de la conformité au droit supérieur de trois des invites de l'IN-3 (art. 68C al. 3 Cst./GE), le Tribunal fédéral revoit librement l'application de cette disposition étroitement liée au droit de vote. L'exigence de motivation, moins élevée, doit alors satisfaire aux conditions de l'<ref-law>. Là encore, les recourants n'émettent aucune critique en lien avec les motifs de l'arrêt attaqué. En effet, ils ne contredisent pas le fait que la commune n'a pas la compétence de délivrer des autorisations de construire et d'instaurer un régime d'interdiction de construire, ni celle d'autoriser des travaux sur le lac. Ils ne contestent pas non plus que l'élaboration d'un dossier pour l'inscription d'un site au patrimoine mondial de l'Unesco n'est pas de la compétence du Conseil municipal mais de celle du Conseil administratif et ne peut donc pas faire l'objet d'une initiative. Loin de répondre à l'argumentation de la cour cantonale, les éléments avancés ne sont, en réalité, qu'un plaidoyer en faveur de l'initiative, rédigé du reste sur un mode purement appellatoire. Partant, les griefs portant sur ce sujet ne satisfont pas aux exigences de motivation de l'<ref-law> et sont aussi irrecevables.
3. Il s'ensuit que le recours est irrecevable. Les frais judiciaires sont mis à la charge des recourants qui succombent (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Les frais judiciaires, arrêtés à 1'000 francs, sont mis à la charge des recourants.
3. Le présent arrêt est communiqué au mandataire des recourants, à la Ville de Genève, au Conseil d'Etat et à la Cour de justice du canton de Genève, Chambre administrative.
Lausanne, le 28 février 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge Présidant: Aemisegger
La Greffière: Tornay Schaller