Faits:
A. L'élection des conseillers municipaux de la commune de Meyrin s'est tenue le 13 mars 2011. Par arrêté du 16 mars 2011, publié dans la Feuille d'avis officielle du canton de Genève le 18 mars 2011, le Conseil d'Etat du canton de Genève (ci-après: le Conseil d'Etat) a constaté les résultats du dépouillement.
A._ s'était présenté comme candidat sur la liste n° 8 intitulée "Diaspora". Cette liste, ayant réuni 9'423 suffrages valables, n'a pas obtenu le quorum légal de 7 %.
B. Le 23 mars 2011, A._ a déposé un recours contre l'arrêté du Conseil d'Etat du 16 mars 2011 auprès de la Chambre administrative de la Cour de justice du canton de Genève (ci-après: la Cour de justice), concluant à l'annulation du scrutin et à la tenue de nouvelles élections. A l'occasion du dépouillement centralisé, le Service des votations et élections du canton de Genève (ci-après: le SVE) avait remarqué une différence de 145 bulletins de vote entre les bulletins entrés et ceux retrouvés. Après diverses recherches, 123 bulletins avaient été retrouvés dans le local du vote, alors que 22 bulletins manquaient. Avant que ne soient retrouvés ces 123 bulletins, la liste "A Gauche Toute" n'obtenait pas le quorum légal. Les 22 bulletins manquants, qui n'avaient toujours pas été retrouvés, représentaient environ 0,5 % des voix électorales. La liste "A Gauche Toute" avait finalement pu atteindre le quorum avec 0,01 %; cela signifiait que ce résultat avait pu être réalisé sur la base d'une seule "voix".
Par courrier du 25 mars 2011, le Conseil d'Etat a répondu au recours. Il a expliqué que, le 10 mars 2011, le SVE avait reçu 3'723 votes par correspondance. Les collaborateurs du SVE ouvraient alors chaque enveloppe grise et vérifiaient qu'elles contenaient une enveloppe bleue et une carte de vote, remplie et signée. L'enveloppe grise était jetée. La carte de vote et l'enveloppe bleue étaient jointes par un trombone. Elles étaient alors triées par local de vote. Le code-barres de la carte de vote était saisi dans le système informatique, pour vérifier la date de naissance de l'électeur et s'assurer que celui-ci ne votait qu'une fois. Si ces informations étaient correctes, la carte de vote et l'enveloppe bleue étaient séparées et les premières étaient regroupées par tas de 50, les secondes également. Quatre tas de 50 enveloppes bleues fermées étaient conditionnés sous vide dans un cellophane, contenant ainsi 200 enveloppes bleues.
En l'espèce, dix-huit paquets de 200 enveloppes bleues, toujours fermées, avaient ainsi été confectionnés (18 x 200 = 3'600), plus un paquet de 123 enveloppes bleues (3'723 - 3'600), emballées de la même manière. Ces 3'723 enveloppes avaient été livrées vendredi 11 mars 2011 par la police au local de vote de Meyrin dans une boîte grise. Les 950 votes par correspondance reçus par le SVE les vendredi et samedi avaient été apportés le dimanche matin au local de vote de Meyrin, par les collaborateurs du SVE. Le dimanche matin 13 mars 2011, 370 électeurs s'étaient rendus au local de vote de Meyrin. Le total des votes enregistrés s'était ainsi élevé à 5'043 (3'723 + 950 + 370). Le prédépouillement avait débuté à 12h. La boîte contenant les bulletins de Meyrin était arrivée à 15h30 à Uni Mail, scellée par le plomb n° 0001541. Lors de la deuxième séance du dépouillement centralisé à 16h30, il avait été annoncé une différence d'environ 150 bulletins: 5'043 votes avaient été enregistrés et 4'898 retrouvés. La directrice du département avait ordonné de retourner dans le local de vote de Meyrin. Après avoir fait ouvrir le local, qui était fermé à clé, un ancien conseiller administratif, accompagné de la police municipale, du concierge et d'un conseiller administratif en fonction, avaient retrouvé à l'intérieur d'un container situé dans le local de vote un paquet, sous vide, contenant les 123 enveloppes bleues toujours fermées, provenant du vote par correspondance. L'emballage en cellophane était intact. Le dépouillement s'était alors poursuivi. Il était apparu que 24 bulletins n'avaient pu être retrouvés. D'une manière générale, lors d'une élection ou d'une votation, il y avait toujours une différence entre les votes enregistrés (cartes de vote) et les votes rentrés (bulletins remplis), le premier chiffre étant supérieur au second. Cela s'expliquait notamment par le fait que certaines enveloppes bleues de vote étaient vides, ou n'étaient pas déposées dans l'urne, ou contenaient autre chose qu'un bulletin. Dans un tel cas, un vote ne pouvait être considéré comme "enregistré", car la carte de vote était arrivée, mais il n'y avait pas de vote "retrouvé" vu l'absence de bulletin. Cette situation pouvait s'expliquer par l'inadvertance de l'électeur, une protestation, voire une tentative, erronée, de vouloir voter blanc. Le Conseil d'Etat donnait ensuite une statistique tendant à démontrer que ce nombre de bulletins qui n'avaient pas été retrouvés se situait dans la norme lors d'autres opérations électorales.
La réponse du Conseil d'Etat a été transmise au recourant le 25 mars 2011, et celui-ci a été invité à indiquer au juge délégué dans les meil-leurs délais s'il souhaitait maintenir son recours.
Le 28 mars 2011, le juge délégué a prié le Conseil d'Etat de bien vouloir lui indiquer si le fait que 24 bulletins étaient "manquants" résultait d'un calcul mathématique ou s'il était établi un décompte des enveloppes bleues qui seraient vides. Le Conseil d'Etat a répondu par courrier du 30 mars 2011, lequel a été transmis au recourant "pour information".
Par arrêt du 31 mars 2011, la Cour de justice a rejeté le recours. Elle a considéré en substance qu'aucune irrégularité de l'opération électorale n'était avérée.
C. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler cet arrêt, de constater que "tout manquement au cheminement sécurisé des bulletins de vote défini aux art. 49 et 66 de la loi genevoise sur l'exercice des droits politiques réalisent une violation fondamentale de la garantie pour une expression fidèle et sûre de la volonté populaire" et que "l'existence de bulletins manquants par simple soustraction des bulletins de vote aux cartes de vote réalise un manquement inacceptable du contrôle du vote et représente une violation fondamentale de la garantie pour une expression fidèle et sûre de la volonté populaire". Il conclut également à ce qu'il soit ordonné à l'Etat de Genève de remédier aux défauts du processus électoral. Il requiert aussi l'assistance judiciaire.
La Cour de justice persiste dans les considérants et le dispositif de son arrêt. La Chancelière d'Etat du canton de Genève, agissant au nom et pour le compte du Conseil d'Etat, conclut au rejet du recours, dans la mesure de sa recevabilité.
D. Par ordonnance du 3 juin 2011, le Juge instructeur a rejeté la requête de mesures provisionnelles, tendant à la suspension de la cérémonie d'assermentation des conseillers municipaux de la commune de Meyrin, que le recourant avait formulée.

Considérant en droit:
1. En vertu de l'art. 82 let. c LTF, le Tribunal fédéral connaît des recours en matière de droit public concernant le droit de vote des citoyens ainsi que les élections et votations populaires. Citoyen de la commune de Meyrin et candidat non élu à l'élection litigieuse, le recourant a la qualité pour recourir (art. 89 al. 1 et 3 LTF). Interjeté en temps utile et dans les formes requises contre une décision finale prise en dernière instance cantonale non susceptible de recours devant le Tribunal administratif fédéral, le recours est recevable au regard des art. 42, 86 al. 1 let. d, 90 et 100 al. 1 LTF.
2. Dans un grief d'ordre formel qu'il convient d'examiner en premier lieu, le recourant se plaint d'une violation de son droit d'être entendu, au motif que la Cour de justice n'a pas ordonné de réplique. En particulier, il n'avait pas pu prendre position sur les réponses du Conseil d'Etat des 25 et 30 mars 2011.
2.1 Le droit d'être entendu est une garantie constitutionnelle de nature formelle, dont la violation entraîne l'annulation de la décision attaquée sans égard aux chances de succès du recours sur le fond (<ref-ruling> consid. 3d/aa p. 437). Ce moyen doit par conséquent être examiné en premier lieu (<ref-ruling> consid. 1 p. 50) et avec un plein pouvoir d'examen (<ref-ruling> consid. 3 p. 194 et la jurisprudence citée).
2.2 Compris comme l'un des aspects de la notion générale de procès équitable au sens des art. 29 Cst. et 6 CEDH, le droit d'être entendu garantit notamment le droit pour une partie à un procès de prendre connaissance de toute argumentation présentée au tribunal et de se déterminer à son propos, que celle-ci contienne ou non de nouveaux éléments de fait ou de droit, et qu'elle soit ou non concrètement susceptible d'influer sur le jugement à rendre. Il appartient en effet aux parties, et non au juge, de décider si une prise de position ou une pièce nouvellement versée au dossier contient des éléments déterminants qui appellent des observations de leur part. Ce droit à la réplique vaut pour toutes les procédures judiciaires. Toute prise de position ou pièce nouvelle versée au dossier doit dès lors être communiquée aux parties pour leur permettre de décider si elles veulent ou non faire usage de leur faculté de se déterminer (<ref-ruling> consid. 4.5; <ref-ruling> consid. 2.2; <ref-ruling> consid. 3.3.2 - 3.3.4; arrêts 5A_791/2010 du 23 mars 2011 consid. 2.3.1; 5D_8/2011 du 8 mars 2011 consid. 2.1; 4D_111/2010 du 19 janvier 2011 consid. 2.1; cf. les arrêts de la Cour européenne des droits de l'homme dans les causes Schaller-Bossert contre Suisse du 28 octobre 2010 § 39 s. et Nideröst-Huber contre Suisse du 18 février 1997, Recueil CourEDH 1997-I p. 101 § 24).
En relation avec une telle communication, le tribunal a la possibilité d'ordonner un second échange d'écritures, ce qu'il fait cependant exceptionnellement (cf. <ref-law>) ou si ces écritures sont estimées nécessaires (art. 74 de la loi genevoise sur la procédure administrative du 12 septembre 1985 [LPA/GE; RSG 5 10]). S'il y renonce, il doit néanmoins transmettre la prise de position ou pièce nouvelle à l'autre ou aux autres parties.
Dans plusieurs affaires concernant la Suisse, la Cour européenne des droits de l'homme a constaté une violation de l'article 6 § 1 CEDH au motif que le recourant n'avait pas été invité à s'exprimer sur les observations d'une autorité judiciaire inférieure, d'une autorité administrative ou de la partie adverse (arrêts de la Cour européenne des droits de l'homme dans les causes Nideröst-Huber contre Suisse du 18 février 1997, § 24, Recueil 1997-I ; F.R. contre Suisse du 28 juin 2001, § 36, ; Ziegler contre Suisse du 21 février 2002, n° 33499/96, § 33; Contardi contre Suisse du 12 juillet 2005, no 7020/02, § 40; Spang contre Suisse du 11 octobre 2005, n° 45228/99, § 28; Ressegatti contre Suisse du 13 juillet 2006, n° 17671/02, § 30; Kessler contre Suisse du 26 juillet 2007, n° 10577/04, § 31; Schaller-Bossert contre Suisse du 28 octobre 2010 § 39 ss; Ellès et autres contre Suisse du 16 décembre 2010 § 26 ss). Dans sa jurisprudence, la Cour européenne des droits de l'homme a notamment affirmé que l'effet réel des observations d'une autorité importe peu, mais que les parties à un litige doivent avoir la possibilité d'indiquer si elles estiment qu'un document appelle des commentaires de leur part. Il y va notamment de la confiance des justiciables dans le fonctionnement de la justice: cette confiance se fonde, entre autres, sur l'assurance d'avoir pu s'exprimer sur toute pièce du dossier (voir, à titre d'exemple, l'arrêt Schaller-Bossert contre Suisse, précité, § 40). Par ailleurs, ladite Cour a considéré qu'un recourant, non représenté par un avocat, n'avait pas à répondre de manière spontanée aux observations litigieuses déposées devant une instance judiciaire pour ne pas renoncer à ses droits découlant de l'article 6 § 1 CEDH, surtout lorsque le courrier par lequel les observations litigieuses ont été adressées au recourant indique clairement la mention "pour information" et que la loi ne prévoit un deuxième échange d'écritures qu'à titre exceptionnel (cf. arrêt Schaller-Bossert contre Suisse, précité, § 42).
2.3 En l'espèce, la Cour de justice a communiqué au recourant, le 25 mars 2011, les déterminations et le chargé de pièces afférent, déposés par le Conseil d'Etat; elle a demandé à celui-là de lui confirmer le maintien de son recours. Le 30 mars 2011, elle a transmis à l'intéressé "pour information", une copie de la réponse fournie par le Conseil d'Etat aux questions posées par le juge délégué à celui-ci le 28 mars 2011. Elle l'a informé que "la cause était gardée à juger". Le lendemain, soit le 31 mars 2011, l'instance précédente a rendu l'arrêt, en se référant notamment aux observations du Conseil d'Etat. Elle a ainsi considéré qu'"au vu des explications qui ont été données [par le Conseil d'Etat] et que les recourants n'ont pas contestées, il apparaît qu'aucune irrégularité de l'opération électorale n'est avérée".
En ne permettant pas au recourant de présenter des observations complémentaires sur les réponses du Conseil d'Etat, alors qu'elles étaient déterminantes pour l'issue du litige, la Cour de justice n'a pas respecté le principe de l'égalité des armes. C'est donc à bon droit que, vu la jurisprudence susmentionnée, récente et stricte, le recourant, au demeurant non assisté d'un avocat, lui reproche d'avoir violé son droit à la réplique.
2.4 La violation du droit d'être entendu précitée ne peut plus être guérie en instance fédérale puisque ce ne sont pas uniquement des questions de droit qui sont controversées mais aussi des questions de fait que le Tribunal fédéral ne peut pas revoir librement (cf. <ref-law>).
3. Le recours doit donc être admis, sans qu'il soit nécessaire d'examiner les autres griefs soulevés par le recourant. La décision attaquée doit par conséquent être annulée et la cause renvoyée à l'autorité précédente pour nouvelle décision prise dans le respect du droit à la réplique défini ci-dessus. Vu l'issue du recours, la demande d'assistance judiciaire est sans objet. Il n'est pas perçu de frais judiciaires (art. 66 al. 1 et 4 LTF) ni alloué de dépens, le recourant ayant agi en personne et n'ayant pas établi avoir assumé des frais particuliers pour la défenses de ses intérêts (arrêt 1C_312/2010 du 8 décembre 2010 consid. 8).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, la décision attaquée est annulée et la cause renvoyée à l'autorité précédente pour nouvelle décision au sens des considérants.
2. Il n'est pas perçu de frais judiciaires et la demande d'assistance judiciaire est sans objet.
3. Le présent arrêt est communiqué au recourant, au Conseil d'Etat et à la Chambre administrative de la Cour de justice du canton de Genève.
Lausanne, le 11 juillet 2011
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Fonjallaz Tornay Schaller