Faits: A. A._ a été placé en détention - provisoire puis pour des motifs de sûreté - du 5 décembre 2012 au 27 mai 2013 dans la prison de Champ-Dollon, dans le cadre d'une procédure pénale dirigée contre lui du chef principal de vols par métier et en bande. Par jugement du 27 mai 2013, le Tribunal de police du canton de Genève a condamné le prénommé à une peine privative de liberté de 20 mois, sous déduction de 175 jours de détention avant jugement, le mettant au bénéfice du sursis et fixant le délai d'épreuve à trois ans. Ce jugement n'a pas fait l'objet d'appel. B. Le 12 avril 2013, A._ a saisi la Présidente du Tribunal de police (rectification d'office: art. 105 al. 2 LTF) d'une demande de mise en liberté, notamment au motif que ses conditions de détention étaient irrégulières et violaient 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 jugement du 4 juin 2013, le Tmc a constaté que, durant 24 jours, les conditions dans lesquelles s'était déroulée la détention provisoire de A._ - pour la surface de la cellule par détenu inférieure à 4 m2, soit 3,84 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. C. 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énié la qualité de partie au Ministère public; sur le fond, il a conclu à la confirmation de la décision entreprise. 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 4 juin 2013. Statuant à nouveau, elle a dit que les conditions de la détention de A._ du 5 décembre 2012 au 27 mai 2013 respectaient les exigences légales. 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 4 juin 2013. Statuant à nouveau, elle a dit que les conditions de la détention de A._ du 5 décembre 2012 au 27 mai 2013 respectaient les exigences légales. D. Agissant par la voie du recours en matière pénale, A._ demande principalement au Tribunal fédéral d'annuler cet arrêt et de confirmer le jugement du Tmc du 4 juin 2013. A titre subsidiaire, il conclut au renvoi de l'affaire à l'autorité cantonale pour statuer à nouveau sur la légalité de sa détention au sens des considérants. 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 a répliqué par courrier du 28 octobre 2013. 