Faits: A. A._ a été placé en détention - provisoire puis pour des motifs de sûreté - du 3 juin 2012 au 24 septembre 2013 dans la prison de Champ-Dollon, dans le cadre d'une procédure pénale dirigée contre lui du chef d'infraction à l'art. 19 ch. 1 et 2 LStup, pour avoir participé à un important trafic de cocaïne. Par jugement du 2 octobre 2013, le Tribunal correctionnel du canton de Genève a condamné le prénommé à une peine privative de liberté de six ans. 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. A l'occasion d'une requête de prolongation de la détention provisoire présentée par le Ministère public du canton de Genève (ci-après: le Ministère public), A._ s'est plaint des conditions de sa détention, faisant valoir une violation 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). Par ordonnance du 17 mai 2013, le Tribunal des mesures de contrainte du canton de Genève (Tmc) a ordonné la prolongation de la détention provisoire; il 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 21 juin 2013, intitulée "jugement en constatation des conditions de détention provisoire", le Tmc a constaté que les conditions dans lesquelles s'est déroulée la détention provisoire de A._ - pour la surface de la cellule par détenu pendant 199 jours, inférieure à 4 m2, soit 3,83 m2, et pour la literie - ne sont 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. A._ ainsi que le Ministère public ont formé appel, respectivement recours contre cette décision: le détenu a conclu à la confirmation du jugement et au constat du caractère illicite de la détention pendant 27 nuits supplémentaires; de son côté, le procureur a soutenu que 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'appui de son recours, A._ a dénié au Ministère public la qualité de partie à la procédure. Par arrêt du 18 septembre 2013, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la cour cantonale) a ordonné la jonction des deux recours: elle a rejeté celui du prévenu et admis celui du Ministère public. Elle a en conséquence annulé la décision du Tmc du 21 juin 2013 et, statuant à nouveau, a dit que les conditions de la détention de A._ du 3 juin 2012 au 29 mai 2013 respectaient les exigences légales. D. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler cet arrêt. A titre principal, il sollicite la réforme de l'arrêt cantonal en ce sens qu'il soit constaté que les conditions dans lesquelles s'est déroulée sa détention étaient illicites. A titre subsidiaire, il conclut au renvoi de l'affaire à l'autorité cantonale pour qu'elle statue à nouveau sur la légalité de sa détention dans le 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é, persistant dans ses précédentes conclusions.