Faits :
A.
Par décision du 23 février 2016, le Département genevois de la Sécurité et de l'économie (ci-après: DSE) a constaté que les conditions dans lesquelles s'était déroulée la détention de X._ entre le 22 janvier et le 1er mai 2013, alors en exécution de peine, étaient licites.
B.
Par arrêt du 27 septembre 2016, la Chambre administrative de la Cour de justice de la République et canton de Genève a rejeté le recours formé par X._ contre la décision du DSE.
En substance, il ressort de l'arrêt entrepris que, du 26 février au 1er mai 2013, X._ partageait une cellule d'une surface nette de 10,18 m2 avec deux autres détenus, de sorte que la surface individuelle nette était de 3,39 m2.
C.
X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt du 27 septembre 2016, dont il demande, à titre principal, la réforme en ce sens qu'une indemnité de 3'250 fr. lui est octroyée pour la détention subie dans des conditions illicites entre le 26 février et le 1er mai 2013. Subsidiairement, il conclut au renvoi de la cause à la cour cantonale; le tout, avec suite de frais et dépens. Il sollicite en outre l'octroi de l'assistance judiciaire, la désignation de Me Hikmat Maleh comme avocat d'office et son indemnisation pour la procédure devant le Tribunal fédéral.
Invités à se déterminer sur le mémoire de recours, la cour cantonale y a renoncé et s'est rapportée à l'arrêt entrepris; le DSE a déposé des observations et a conclu au rejet du recours dans la mesure de sa recevabilité. Informé des prises de position, X._ a persisté intégralement dans les conclusions et griefs de son recours.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2.1 p. 397; <ref-ruling> consid. 2 p. 59).
1.1. L'indemnisation de conditions de détention illicites après jugement relève des normes ordinaires en matière de responsabilité de l'Etat (cf. arrêt 6B_703/2016 du 2 juin 2017 consid. 2.1).
Le litige porte sur l'éventuelle responsabilité de l'Etat de Genève à l'égard du recourant et l'arrêt attaqué peut en principe faire l'objet d'un recours en matière de droit public au Tribunal fédéral (<ref-law>; arrêt 6B_703/2016 du 2 juin 2017 consid. 1). La Cour de droit pénal est compétente pour traiter un tel recours (art. 30 al. 1 let. c ch. 1 et art. 33 du règlement du Tribunal fédéral [RS 173.110.131]; <ref-ruling> consid. 1.1.2 p. 46).
La voie du recours en matière pénale indiquée dans l'arrêt entrepris (cf. art. 112 al. 1 let. d LTF) est erronée. Le mémoire de recours sera converti d'office en recours en matière de droit public, respectivement en recours constitutionnel subsidiaire, dans la mesure où il remplit les conditions de recevabilité (<ref-ruling> consid. 1.2 p. 382 s.; arrêt 6B_387/2012 du 25 février 2013 consid. 1.1).
1.2. En matière de responsabilité étatique, le recours en matière de droit public n'est recevable que si la valeur litigieuse s'élève au moins à 30'000 francs (<ref-law>). En cas de recours contre une décision finale, cette valeur est déterminée par les conclusions - recevables - restées litigieuses devant l'autorité précédente juste avant que celle-ci prononce le jugement (<ref-law>).
En l'espèce, le recourant a chiffré à 3'250 fr. ses prétentions en indemnisation, rejetées par l'autorité précédente (arrêt entrepris, consid. 7 p. 3). Auprès du Tribunal fédéral, le recourant conclut au paiement de la même somme, laquelle n'atteint pas la valeur litigieuse minimale prévue à l'<ref-law>. Il ne soulève pas de question juridique de principe (<ref-law>; cf. sur cette notion, <ref-ruling> consid. 4 p. 342 s., 138 I 232 consid. 2 p. 235 s., le recourant doit exposer en quoi l'affaire remplit cette exigence). Le recours en matière de droit public est irrecevable.
1.3. En tant que le recourant fait valoir une violation de l'art. 3 CEDH (interdiction de traitements inhumains ou dégradants), il invoque un droit de nature constitutionnelle (<ref-ruling> consid. 1.3.1 p. 80; cf. JEAN-MAURICE FRÉSARD, in Commentaire de la LTF, 2e éd., 2014, n° 3 ad <ref-law>). En cela, le recours constitutionnel subsidiaire est ouvert (cf. <ref-law>).
2.
Le recourant reproche à la cour cantonale d'avoir violé l'art. 3 CEDH en considérant que ses conditions de détention du 26 février au 1er mai 2013 étaient licites. Il relève notamment la durée de sa détention, l'espace individuel à disposition, le confinement et les conditions de literie.
2.1. L'art. 3 CEDH prévoit que nul ne peut être soumis à la torture ni à des peines ou traitements inhumains ou dégradants. Sur le plan constitutionnel, l'art. 7 Cst. prescrit de son côté que la dignité humaine doit être respectée et protégée. A teneur de l'art. 10 al. 3 Cst., la torture et tout autre traitement ou peine cruels, inhumains ou dégradants sont interdits. En se référant à la Recommandation Rec (2006) 2 sur les Règles pénitentiaires européennes (ci-après: RPE) édictée par le Comité des ministres du Conseil de l'Europe le 11 janvier 2006, ainsi qu'au Commentaire de ces règles émanant du Comité européen pour la prévention de la torture et des peines ou traitements inhumains ou dégradants (CPT), la jurisprudence a déduit de l'art. 3 CEDH ainsi que des autres normes protégeant la dignité humaine, en droit international et en droit interne, un certain nombre de critères permettant d'évaluer si les conditions concrètes de détention se situent en deçà ou au-delà du seuil du traitement inhumain ou dégradant.
Un traitement dénoncé comme contraire à l'art. 3 CEDH doit atteindre un niveau d'humiliation ou d'avilissement supérieur à ce qu'emporte habituellement la privation de liberté. La gravité de cette atteinte est appréciée au regard de l'ensemble des données de la cause, considérées globalement, notamment de la nature et du contexte du traitement ainsi que de sa durée (<ref-ruling> consid. 6.3.4 p. 146 s.; <ref-ruling> consid. 4 p. 278 et les arrêts cités). Celle-ci est susceptible de rendre incompatible avec la dignité humaine une situation qui ne le serait pas nécessairement sur une courte période. Sans viser à l'exhaustivité, il s'agit d'apprécier, notamment, si le lieu de détention répond à des exigences minimales quant à l'hygiène (propreté; accès aux installations de bain et de douche et aux sanitaires; protection de l'intimité), à la literie, à la nourriture (régime alimentaire; hygiène de la préparation et de la distribution; accès à l'eau potable), à l'espace au sol, au volume d'air, à l'éclairage et à l'aération, en tenant compte notamment des conditions climatiques locales et des possibilités d'effectuer des exercices à l'air libre (arrêt 6B_688/2015 du 19 mai 2016 consid. 7.2).
S'agissant de l'espace au sol, le Tribunal fédéral a jugé qu'en cas de surpopulation carcérale telle que la connaît la prison de Champ-Dollon, l'occupation d'une cellule dite individuelle par trois détenus - chacun disposant d'un espace individuel de 4 m2 restreint du mobilier - est une condition difficile mais ne représente pas un traitement dégradant portant atteinte à la dignité humaine des détenus. En revanche, l'occupation d'une cellule dite triple par six détenus avec une surface individuelle de 3,83 m2 - restreinte encore par le mobilier - peut constituer une violation de l'art. 3 CEDH si elle s'étend sur une longue période (s'approchant, à titre indicatif, de trois mois) et si elle s'accompagne d'autres mauvaises conditions de détention, en particulier lorsque le détenu n'est autorisé qu'à passer un temps très limité hors de sa cellule (une heure de promenade en plein air par jour; voir <ref-ruling> consid. 3.6.3 p. 138 ss; voir aussi l'arrêt 6B_456/2015 du 21 mars 2016 consid. 2.1 et les arrêts cités).
2.2. Dans deux affaires récentes, le Tribunal fédéral s'est prononcé sur les questions de conditions de détention subie dans un espace individuel de 3,39 m2 pour une durée avoisinant le délai indicatif de trois mois (arrêts 6B_1314/2015 du 10 octobre 2016 consid. 4; 6B_794/2015 du 15 août 2016 consid. 2). D'autres cas portent sur des durées largement supérieures (cf. arrêts 6B_946/2015 du 13 septembre 2016 consid. 3 [environ 534 jours]; 6B_916/2015 du 15 août 2016 consid. 1 [implicitement, environ 458 jours]; 1B_239/2015 du 29 septembre 2015 consid. 2 [environ 328 jours]).
La période de 71 jours durant laquelle un détenu a disposé d'un espace individuel de 3,39 m2, confiné pendant 23h/24h a été jugée contraire à l'art. 3 CEDH, ce d'autant qu'il arrivait au détenu de dormir sur un matelas posé à même le sol (arrêt 6B_794/2015 du 15 août 2016 consid. 2.2).
Dans un cas impliquant un détenu disposant, pendant 98 jours, d'une surface individuelle de 3,39 m2, le Tribunal fédéral a considéré que la détention respectait les standards conventionnels. Dans l'appréciation, il a été tenu compte des conditions concrètes de détention (notamment hygiène et activité hors cellule d'un codétenu). L'arrêt ne contient pas d'indication quant au confinement (arrêt 6B_1314/2015 du 10 octobre 2016 consid. 4.2).
Il résulte de la jurisprudence que, pour des durées de détention dans un espace individuel net de 3,39 m2, légèrement inférieures ou supérieures au délai indicatif de trois mois, il y a lieu de tenir compte des circonstances concrètes du cas d'espèce pour admettre, respectivement dénier le caractère illicite des conditions de détention.
2.3. S'agissant en particulier des questions de literie, la règle 21 de la RPE recommande que chaque détenu dispose d'un lit séparé et d'une literie individuelle convenable, entretenue correctement et renouvelée à des intervalles suffisamment rapprochés pour en assurer la propreté. Dans son commentaire, le CPT expose qu'un lit doit comprendre un sommier, un matelas et une couverture par détenu.
Selon la jurisprudence de la CourEDH, des mauvaises conditions de détention relatives à la literie (prisonniers contraints de dormir à tour de rôle, partageant leur lit, dormant à même le sol), ajoutées à d'autres facteurs, tels que l'exiguïté des cellules et le confinement, peuvent emporter une violation de l'art. 3 CEDH (cf. notamment arrêts CourEDH Cîrnici contre Roumanie du 26 janvier 2016 ; Grishin contre Russie du 15 novembre 2007 ; Kalachnikov c. Russie du 15 juillet 2002; Peers contre Grèce du 19 avril 2001; cf. également les nombreux arrêts cités dans l'opinion dissidente des Juges Zagrebelsky et Jociené de l'arrêt CourEDH Sulejmanovic contre Italie du 16 juillet 2009). Dans une affaire traitant de détenus contraints de dormir sur des matelas posés par terre, la CourEDH a retenu une violation de l'art. 3 CEDH en tenant compte notamment de la durée de la détention (entre une année et 5 ans, selon les détenus concernés), de la surface disponible (entre 2,10 m2et 3,57 m2), de l'hygiène (matelas et couverture dans un état crasseux) et du chauffage défectueux (arrêt CourEDH Bouros et autres contre Grèce du 12 mars 2015, § 48-50 et 80).
Le Tribunal fédéral a considéré que, si le fait de dormir dans une literie sans sommier à même le sol pendant un nombre incertain de nuits n'était pas strictement conforme à l'art. 21 RPE, cela n'était pas nécessairement constitutif de traitement inhumain au sens de l'art. 3 CEDH, ce d'autant moins si le renouvellement fréquent de la literie n'était pas contesté (cf. <ref-ruling> consid. 3.6.4 p. 141; arrêt 1B_404/2013 du 26 février 2014 consid. 2.6.3).
2.4. A teneur de la décision du DSE du 23 février 2016, le recourant a occupé du 26 février au 1er mai 2013, une cellule dont l'espace individuel à disposition était de 3,39 m2 durant 60 jours, à savoir pendant 13 jours (du 26 février au 10 mars), puis 47 jours (du 16 mars au 1er mai), ces deux périodes étant entrecoupées par 5 jours durant lesquels il disposait d'un espace individuel net de 5,09 m2 (cellule occupée par deux détenus).
S'agissant des autres conditions de détention, le DSE s'est fondé sur les informations transmises par la Direction de la prison de Champ-Dollon et a retenu que les draps de lits étaient renouvelés toutes les deux semaines et que les taies d'oreiller ainsi que les linges de bain étaient changés toutes les semaines. Le ménage des cellules était assuré par les occupants de la cellule auxquels des produits d'entretien étaient remis et les cours de promenades étaient nettoyées toutes les semaines par le service d'entretien extérieur qui y consacrait deux journées. Le recourant bénéficiait d'une heure de sport hebdomadaire et a reçu 22 visites durant la période litigieuse. Le DSE a alors estimé que la période de 60 jours de détention effectuée dans une cellule offrant un espace individuel net de 3,39 m2 n'était pas suffisante pour consacrer une illicéité.
La cour cantonale a relevé la durée totale de 64 jours (du 26 février au 1er mai 2013) et a constaté qu'elle était inférieure au seuil de trois mois évoqué par le Tribunal fédéral. Elle a considéré que la prise des repas en cellule était comprise dans le temps de confinement, que la cour de promenade n'était pas insalubre mais sale et que les conditions d'hygiène de la literie étaient convenables. Il en allait de même de l'état d'hygiène et d'aération et de l'approvisionnement en eau, nourriture, chauffage et lumière. La cour cantonale en a déduit que les conditions de détention durant la période pertinente étaient licites.
2.5. En l'espèce, le recourant a été détenu pendant 60 jours, non consécutifs, dans une cellule individuelle occupée par trois détenus, offrant un espace individuel de 3,39 m2. Il ne ressort pas du dossier que cette période suivrait ou précéderait de près une autre dans laquelle les conditions de détention ne respectaient pas les standards de la CEDH, le recourant ne le prétend d'ailleurs pas. A teneur de l'arrêt entrepris, le recourant a été transféré le 1er mai 2013. Le recourant se réfère intégralement aux faits établis par la cour cantonale (cf. mémoire de recours, ch. II), lesquels lient le Tribunal fédéral (<ref-law>). En particulier, le recourant ne fait pas valoir d'arbitraire dans l'établissement des faits quant à l'état de la cour de promenade ni quant aux conditions d'hygiène (art. 97 al. 1 et 106 al. 2 LTF). Il ne conteste pas qu'en termes d'hygiène, d'aération, d'accès à l'eau ou de soins, les conditions de détention étaient convenables.
L'aménagement d'une heure de promenade quotidienne, sans autre possibilité régulière de sortir de sa cellule, ne constitue en principe pas à elle seule un traitement prohibé (cf. arrêt 1B_404/2013 du 26 février 2014 consid. 2.6.3). Tel peut être le cas lorsque cette promenade s'effectue dans une cour de taille très réduite (arrêt CourEDH Aleksandr Makarov contre Russie du 12 mars 2009, § 95). Il ne ressort cependant ni des allégations du recourant, ni du dossier que tel aurait été le cas. Quant à la prise de repas en cellule, il en est tenu compte dans le critère de confinement et ne constitue pas un facteur aggravant en soi.
Si les conditions de détention subies par le recourant étaient difficiles, elles ont toutefois duré deux mois non consécutifs, à savoir un tiers en deçà du seuil indicatif de trois mois évoqué par la jurisprudence. Dans ces circonstances, l'on ne saurait retenir une violation de l'art. 3 CEDH, quand bien même le recourant était alors en exécution de peine. Il est relevé à cet égard que la jurisprudence européenne ne fait apparaître aucune distinction entre les détenus condamnés et ceux qui sont dans l'attente de leur procès pour ce qui est de l'application de la norme minimale de 3 m2 de surface au sol par détenu en cellule collective (Arrêt CourEDH Mursic contre Croatie du 20 octobre 2016, § 115 et les arrêts cités).
2.6. En prétendant qu'il était contraint de dormir sur un matelas posé à même le sol durant vingt nuits, le recourant se fonde sur un fait qui ne ressort pas de l'arrêt entrepris, sans invoquer l'arbitraire de son omission (cf. <ref-law>). Si la cour cantonale a reproduit les plaintes du recourant sur ce point (cf. arrêt entrepris, consid. 7 p. 3), elle ne l'a pas tenu pour établi. Certes le rapport du Directeur de la prison de Champ-Dollon du 16 septembre 2015 expose qu'un troisième détenu placé dans une cellule individuelle a, éventuellement, pu dormir sur un matelas posé à même le sol. Ce document n'identifie toutefois pas le détenu et ajoute que les cellules concernées ont été équipées, en septembre 2013, d'un lit rabattable. En tout état, à supposer que, comme il l'allègue, le recourant a dormi pendant 5, puis 15 nuits (20 nuits en tournus sur les périodes de 13 et 47 jours) sur un matelas posé au sol, cela n'atteint pas un seuil de gravité suffisant pour constituer un traitement inhumain et dégradant au sens de l'art. 3 CEDH, étant établi que la literie était changée régulièrement (cf. <ref-ruling> consid. 3.6.4 p. 141; arrêt 1B_404/2013 du 26 février 2014 consid. 2.6.3). Le cas d'espèce se distingue largement d'affaires impliquant des conditions de literie jugées, parmi d'autres conditions défavorables, contraires à l'art. 3 CEDH (cf. supra consid. 2.3).
2.7. Au regard de l'ensemble des données de la cause, étant relevé notamment que le recourant a été transféré d'établissement à la fin de la période litigieuse, ses conditions de détention, s'étendant sur 60 jours non consécutifs, n'ont pas atteint le seuil de gravité minimum pour emporter une violation de l'art. 3 CEDH.
Partant, pour la période allant du 26 février au 1er mai 2013, la cour cantonale pouvait considérer, sans violer le droit fédéral, que les conditions de détention du recourant, pour difficiles qu'elles aient été, respectaient les exigences constitutionnelles et étaient conformes à l'art. 3 CEDH.
Il en découle qu'il n'y a pas lieu d'entrer en matière sur la conclusion tendant à l'octroi d'une indemnité pour détention dans des conditions illicites.
3.
Le recours doit être rejeté dans la mesure où il est recevable. Dès lors que le recourant est dans le besoin et que ses conclusions ne paraissaient pas dénuées de chances de succès, sa requête d'assistance judiciaire doit être admise (<ref-law>). Par conséquent, il y a lieu de le dispenser des frais et d'allouer une indemnité à son mandataire, désigné comme avocat d'office (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La requête d'assistance judiciaire est admise. Me Hikmat Maleh est désigné comme conseil d'office et une indemnité de 3'000 fr. lui est allouée à titre d'honoraires, à payer par la caisse du Tribunal fédéral.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lausanne, le 31 octobre 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke