Faits:
A. Par décision du 11 juin 2012, le Ministère public du canton de Genève a refusé d'entrer en matière sur la plainte du 18 novembre 2011 déposée par A._ pour diffamation contre C._, son avocat B._ et tout autre participant. Dans sa plainte, A._ reprochait aux intéressés d'avoir communiqué, le 21 octobre 2011, dans le cadre d'une procédure prud'homale - opposant C._ à une ancienne employée de maison, assistée par A._ -, un procès-verbal d'audience du 17 octobre 2011 du Tribunal de police faisant état d'une précédente inculpation de A._ en 1999; ce document consignait les propos tenus dans la procédure pénale pour calomnie ouverte contre A._ sur plainte de C._.
Le 22 juin 2012, A._ a recouru contre cette décision de non-entrée en matière, concluant à l'ouverture d'une instruction pour diffamation, voire calomnie ou au prononcé d'une ordonnance pénale; il a conclu à l'octroi de dépens, subsidiairement à l'octroi de l'assistance judiciaire gratuite.
Aux termes d'un arrêt rendu le 16 août 2012, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice ou la cour cantonale) a annulé cette décision et renvoyé le dossier au Ministère public pour suite de la procédure, au sens des considérants. Il a mis, à la charge de B._, les frais de la procédure de recours. La Cour de justice a déclaré irrecevable la conclusion du plaignant tendant à l'octroi de dépens, faute pour celui-ci de les avoir chiffrés et justifiés. Elle a également écarté la demande subsidiaire d'assistance judiciaire formée par le plaignant; celui-ci n'avait pas justifié son indigence au sens de l'<ref-law>; en outre, ses revenus et charges tels qu'établis par le Tribunal de police (jugement du 17 octobre 2011) lui permettaient d'assumer les frais de sa défense dans la présente procédure; il ne semblait pas avoir bénéficié d'une défense d'office devant le Tribunal de police et n'avait pas demandé l'assistance judiciaire en déposant la plainte du 18 novembre 2011, un mois plus tard.
B. A._ forme un recours contre cet arrêt. Il en demande l'annulation dans la seule mesure où il rejette la requête d'assistance judiciaire pour la procédure de recours. Il conclut à l'octroi de l'assistance judiciaire pour la procédure de recours devant la Cour de justice avec effet au 22 juin 2012 ainsi qu'au renvoi de la cause à l'instance précédente pour taxer l'intervention de l'avocat d'office et examiner si l'indemnité allouée à son avocat doit être mise à la charge des prévenus en application de l'<ref-law>. Il demande enfin l'assistance judiciaire pour la procédure devant le Tribunal fédéral. Il se plaint d'une violation des art. 29 al. 3 Cst. et 136 al. 1 CPP, les conditions de l'indigence étant réalisés; subsidiairement, il se plaint d'une violation de son droit d'être entendu dans la mesure où la Cour de justice ne lui a pas accordé le délai requis dans son courrier du 22 juin 2012 pour fournir les pièces attestant son état d'indigence.
La Cour de justice et le Ministère public se sont référés à l'arrêt entrepris. Invité à se déterminer, l'intimé a conclu au rejet du recours aux termes de ses observations.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis.
1.1 En vertu de l'<ref-law>, le recours en matière pénale au Tribunal fédéral est recevable contre les décisions qui mettent fin à la procédure. Il est également recevable contre certaines décisions préjudicielles et incidentes. Il en va ainsi de celles qui concernent la compétence et les demandes de récusation (<ref-law>). Quant aux autres décisions préjudicielles et incidentes notifiées séparément, elles peuvent faire l'objet d'un recours si elles peuvent causer un préjudice irréparable (<ref-law>) ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (<ref-law>).
L'objectif poursuivi par cette disposition est de décharger le Tribunal fédéral en faisant en sorte que, dans la mesure du possible, celui-ci soit amené à trancher l'ensemble du litige dans une seule décision (<ref-ruling> consid. 1.3.2 p. 34). Les exceptions permettant de recourir contre une décision préjudicielle ou incidente doivent donc être appréciées restrictivement, ce d'autant que les parties n'en subissent en principe pas de préjudice, puisqu'elles peuvent encore attaquer la décision préjudicielle ou incidente avec la décision finale en vertu de l'<ref-law> (arrêt 8C_817/2008 du 19 juin 2009 consid. 4.2.1).
1.2 L'arrêt attaqué, qui annule la décision de non-entrée en matière du 11 juin 2012 et renvoie la cause pour suite de l'instruction au Ministère public, ne met pas fin à la procédure pénale; il s'agit, tant sur le fond (<ref-ruling> consid. 4.2 p. 481 s.) qu'en ce qui concerne le refus de l'assistance judiciaire (<ref-ruling> consid. 1a p. 253 et la jurisprudence citée), d'une décision incidente.
En l'espèce, le recours est dirigé contre l'arrêt entrepris "dans la seule mesure où il rejette la requête d'assistance judiciaire du recourant pour la procédure de recours". Le plaignant conclut ainsi à l'octroi de l'assistance judiciaire pour la procédure de recours devant la Chambre pénale de recours, ceci avec effet au 22 juin 2012 - date du dépôt de son mémoire de recours - (cf. conclusions n° 2 et 3).
Dans un tel cas, le recours n'est ouvert que si cette décision incidente peut causer un préjudice irréparable (<ref-law>), la seconde exception prévue à l'<ref-law> n'étant pas pertinente en l'espèce.
1.3 Dans la procédure de recours en matière pénale, la notion de préjudice irréparable se rapporte à un dommage de nature juridique qui ne peut pas être réparé ultérieurement par un jugement final ou une autre décision favorable au recourant (<ref-ruling> consid. 2.1 p. 173).
D'après la jurisprudence, le refus de l'assistance judiciaire dans une cause pénale est susceptible de causer un préjudice irréparable. Le préjudice que peut subir une personne non assistée dans une procédure pénale peut difficilement être réparé ultérieurement par une nouvelle procédure intervenant à la suite du succès d'un recours contre le refus d'assistance gratuite. Souvent, l'administration des preuves en première instance est en effet déterminante pour l'issue du procès (cf. <ref-ruling> consid. 4 p. 338 et les références). La présente situation est différente: en effet, la procédure cantonale de recours pour laquelle l'assistance judiciaire a été demandée par le recourant est maintenant terminée, la cause ayant été renvoyée au Ministère public pour suite de la procédure. Le recourant n'a donc pas été privé de l'assistance d'un avocat durant la procédure devant la Cour de justice; il ne court plus le risque de ne pas voir ses droits exercés (cf. <ref-ruling> consid. 2.2 p. 647 s.; arrêt 8C_530/2008 du 25 septembre 2008 consid. 2.3). En réalité, il s'agit ici uniquement de déterminer qui devra, en définitive, assumer les frais d'avocat du recourant. Par conséquent, le recourant ne subit pas de préjudice irréparable au sens de la jurisprudence.
Par ailleurs, le recourant pourra formuler ses griefs, pour autant que nécessaire, à l'occasion de la contestation de la décision finale (<ref-law>). Enfin, il convient de relever que, dans le cadre de la procédure pénale de première instance dirigée par le Ministère public, le recourant conserve la possibilité de solliciter l'octroi de l'assistance judiciaire, ce qu'il n'a pas fait jusqu'à présent.
1.4 Il résulte de ce qui précède que le recours doit être déclaré irrecevable. Compte tenu des circonstances, le présent arrêt sera rendu sans frais (<ref-law>). Les conclusions du recours étant cependant vouées à l'échec, la demande d'assistance judiciaire présentée pour la procédure de recours devant le Tribunal fédéral doit être rejetée (art. 64 al. 1 et 2 LTF). Enfin, l'intimé, assisté d'un avocat, a droit à des dépens, à la charge du recourant (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. La demande d'assistance judiciaire est rejetée.
3. Il n'est pas perçu de frais judiciaires.
4. Une indemnité de 600 fr. est allouée à l'intimé à titre de dépens, à la charge du recourant.
5. Le présent arrêt est communiqué aux mandataires des parties, au Ministère public et à la Cour de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 11 avril 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
La Greffière: Arn