Faits: A. A._ a été placé en détention - provisoire puis pour des motifs de sûreté - du 26 juin 2012 au 2 août 2013 dans la prison de Champ-Dollon, dans le cadre d'une procédure pénale dirigée contre lui notamment pour tentative de meurtre. Par jugement du 19 juin 2013, le Tribunal correctionnel du canton de Genève l'a condamné à une peine privative de liberté de 36 mois, à raison de 15 mois ferme et de 21 mois avec sursis; ses conclusions en indemnisation au titre de tort moral fondées sur sa prétendue détention illicite de 359 jours ont été rejetées. La question des conditions de la détention de A._ n'a pas été évoquée dans ce contexte. L'intéressé a formé appel de ce jugement. La cause est actuellement pendante auprès de la juridiction d'appel. B. Le 5 juin 2013, A._ a saisi le Ministère public du canton de Genève (ci-après: le Ministère public) d'une demande de mise en liberté au motif que ses conditions de détention ne respectaient pas les normes minimales découlant de l'art. 3 de la Convention de sauvegarde des droits de l'homme et des libertés fondamentales, entrée en vigueur pour la Suisse le 28 novembre 1974 (CEDH; RS 0.101). Cette requête a été rejetée, en dernier lieu par le Tribunal des mesures de contrainte du canton de Genève (Tmc), lequel a néanmoins ouvert une procédure afin de vérifier si, dans le cas particulier, avaient été commises des irrégularités susceptibles de constituer une violation de la CEDH, du droit fédéral ou du droit cantonal. Par décision du 5 juillet 2013, intitulée "jugement en constatation des conditions de la détention provisoire", le Tmc a constaté que les conditions dans lesquelles s'est déroulée la détention provisoire de A._ du 26 juin 2012 au 9 juin 2013 - pour la surface de la cellule par détenu pendant 89 jours inférieure à 4 m2, soit 3,83 m2 - n'étaient pas conformes aux règles pénitentiaires européennes. Cette décision précisait qu'elle pouvait faire l'objet d'un appel auprès de la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève. Le Ministère public a formé appel, respectivement recours contre cette décision: selon lui, les exigences légales, constitutionnelles et conventionnelles en matière de conditions de détention avaient été respectées, de sorte que A._ devait être entièrement débouté. A l'occasion de sa réponse, celui-ci a déclaré former appel de la décision du 5 juillet 2013 concluant à ce qu'il soit constaté que sa détention n'avait pas été conforme aux règles en vigueur pendant 329 jours. Par arrêt du 22 août 2013, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la cour cantonale) a annulé la décision du Tmc du 5 juillet 2013. Statuant à nouveau, elle a dit que les conditions de la détention de A._ du 26 juin 2012 au 9 juin 2013 respectaient les exigences légales. Elle a considéré en substance que les conditions de la gravité et de la persistance, sur une longue durée, de prétendus mauvais traitements, telles qu'exigées par la CourEDH pour fonder une violation de l'art. 3 CEDH, n'étaient pas réalisées en l'espèce. C. Agissant par la voie du recours en matière pénale, A._ demande principalement au Tribunal fédéral de réformer l'arrêt cantonal en ce sens qu'il soit constaté que les conditions dans lesquelles s'est déroulée sa détention du 26 juin 2012 au 9 juin 2013 ne sont pas conformes aux standards légaux. A titre subsidiaire, il conclut au renvoi de l'affaire à l'autorité cantonale pour statuer à nouveau sur la légalité de sa détention. Il requiert enfin l'octroi de l'assistance judiciaire. Le Ministère public conclut au rejet du recours. La cour cantonale se réfère aux considérants de sa décision. Le recourant n'a pas souhaité faire d'observations supplémentaires. 