Faits: A. A._ a été placé en détention - provisoire puis pour des motifs de sûreté - du 16 février 2013 au 29 novembre 2013 dans la prison de Champ-Dollon, dans le cadre d'une procédure pénale dirigée contre lui notamment pour tentative de contrainte, lésions corporelles simples qualifiées et dommage à la propriété. Il a été renvoyé en jugement devant le Tribunal de police par acte d'accusation du Ministère public du 26 août 2013. B. Le 10 mai 2013, A._ a sollicité sa mise en liberté immédiate, alléguant notamment que les conditions de détention n'étaient plus conformes à 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) et qu'il avait été agressé et menacé par d'autres détenus. Par ordonnance du 21 mai 2013, le Tribunal des mesures de contrainte du canton de Genève (Tmc) a refusé la mise en liberté du prénommé; 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 ordonnance du 2 septembre 2013, intitulée "ordonnance 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._ du 16 février 2013 au 29 mai 2013 respectaient les exigences légales. 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 de justice) a rejeté le recours déposé par A._ contre cette ordonnance. 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 d'annuler cet arrêt, de constater l'illicéité de sa détention et de lui octroyer une indemnité de 200 francs par jour de détention. 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 renonce à présenter des observations.