Faits:
A. A.a M._, né en 1950, travaillait comme couvreur. Le 3 août 1992, il a chuté lourdement sur le dos. Souffrant de douleurs lombaires, il a déposé le 29 juillet 1994 une demande de prestations d'invalidité auprès de l'Office de l'assurance-invalidité du canton de Genève (ci-après: l'OAI), laquelle a été rejetée par décision du 1er novembre 1994.
A.b Le 7 juillet 1995, l'assuré a présenté une nouvelle demande de prestations. Dans le cadre de l'instruction de la cause, l'OAI a recueilli les renseignements usuels auprès des médecins traitants. Le docteur L._, spécialiste FMH en orthopédie, a estimé que la capacité de travail était nulle dans l'activité habituelle, mais pouvait être améliorée par des mesures médicales; des mesures professionnelles étaient indiquées (rapport du 16 août 1995). Les docteur H._, spécialiste FMH en médecine physique et rééducation et P._, spécialiste FMH en médecine interne et rhumatologie, ont indiqué que la capacité de travail pourrait être entière dans une activité adaptée (rapports du 18 août 1995 respectivement du 15 décembre 2002). La réalisation d'une expertise a été confiée au docteur D._, spécialiste FMH en médecine interne et rhumatologie, qui a conclu à l'exigibilité d'un travail à temps complet dans une activité ne nécessitant ni port de charges excédant 3 à 4 kilogrammes, ni mouvements réguliers du buste vers l'avant (rapport du 2 juin 2003). Interpellés par l'OAI, les docteurs S._, spécialiste FMH en chirurgie et médecin traitant, et P._ ont indiqué qu'ils partageaient les conclusions de l'expert (courriers du 20 respectivement du 23 juin 2003).
Deux stages d'observation professionnelle auprès du Centre d'intégration professionnelle X._ (du 26 janvier au 22 février 2004 et du 5 avril au 4 juillet 2004) ont mis en évidence une capacité de travail de 60 % dans une activité adaptée (rapports des 16 mars et 28 juillet 2004).
L'OAI a ensuite mandaté le docteur C._, spécialiste FMH en médecine interne et rhumatologie, lequel a conclu à une capacité de travail entière dans une activité excluant le port de charges de plus de 10 kilogrammes, les mouvements répétitifs d'abduction et de rotations externes et les activités au-dessus de l'horizontale avec le membre supérieur gauche (rapport du 25 juin 2009).
Par décision du 18 février 2010, l'OAI a considéré - compte tenu d'une capacité de travail entière et d'un abattement de 15 % sur le revenu selon l'Enquête suisse sur la structure des salaires (ESS) - que le taux d'invalidité était de 19 %, insuffisant pour ouvrir le droit à l'intéressé à une rente ou à des mesures de réadaptation professionnelle.
B. L'assuré a déféré cette décision au Tribunal cantonal des assurances sociales de la République et canton de Genève (aujourd'hui: la Cour de justice de la République et canton de Genève, Chambre des assurances sociales).
Le 2 juin 2010, l'assuré a été victime d'une crise cardiaque. Selon le docteur R._, spécialiste FMH en médecine générale et cardiologie, cet événement n'a pas affecté sa capacité de travail (courrier du 3 décembre 2010). Interpellé par l'instance cantonale, le docteur C._ a confirmé les conclusions de son expertise tandis que le docteur A._, spécialiste FMH en médecine interne et médecin traitant, a retenu une capacité de travail de 30 à 40 % (courriers du 6 respectivement du 21 décembre 2010).
Le docteur O._, spécialiste FMH en médecine pratique et médecin du travail auprès du SMR, a considéré que dans l'activité habituelle, la capacité de travail de l'assuré avait été de 50 % de 1995 à janvier 2002 et nulle depuis lors; dans une activité adaptée, elle avait toujours été entière, avec cependant une baisse de rendement de 20 % dès le 2 juin 2010, en raison de ses atteintes cardiaque et osthéoarticulaire (avis du 17 janvier 2011).
Par jugement du 3 mai 2011, l'instance cantonale a admis partiellement le recours, octroyé à l'assuré une demi-rente d'invalidité dès le 1er septembre 2010 et renvoyé la cause à l'OAI pour le calcul du montant de la rente.
C. M._ et l'Office cantonal genevois de l'assurance-invalidité interjettent l'un et l'autre un recours en matière de droit public contre ce jugement dont ils demandent l'annulation. L'assuré conclut principalement à l'octroi d'un quart de rente au minimum de janvier 2002 à juin 2010 et d'une rente entière à partir de septembre 2010 au plus tard, subsidiairement au renvoi de la cause à l'instance cantonale, éventuellement à l'OAI, pour nouvelle décision au sens des considérants. Il assortit son recours d'une requête d'assistance judiciaire. De son côté, l'OAI conclut à la confirmation de sa décision du 18 février 2010.
L'OAI conclut au rejet du recours de l'assuré, tandis que ce dernier et l'Office fédéral des assurances sociales ont renoncé à se déterminer.

Considérant en droit:
1. Les deux recours sont dirigés contre le même jugement, opposent les mêmes parties et concernent le même complexe de faits, de sorte qu'il se justifie de les réunir et de les liquider dans un seul arrêt (<ref-ruling> consid. 1 p. 60 s., 128 V 192 consid. 1 p. 194, 123 V 214 consid. 1 p. 215 s.).
2. Le recours en matière de droit public peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral fonde son raisonnement sur les faits retenus par la juridiction de première instance (<ref-law>) sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). La partie recourante qui entend s'écarter des faits constatés doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> sont réalisées sinon un état de fait divergent ne peut être pris en considération.
3. 3.1 Est litigieux le droit de l'assuré à une rente de l'assurance-invalidité depuis janvier 2002. Le jugement entrepris expose de manière complète les règles légales et les principes jurisprudentiels sur la notion d'invalidité et la valeur probante des rapports médicaux. Il suffit d'y renvoyer.
4. En tenant compte des opinions exprimées par les docteurs D._, H._, S._, C._ et P._ notamment, les premiers juges ont estimé qu'en 2002, la capacité de travail de l'assuré était entière. Les avis pour l'essentiel convergents de ces médecins ne pouvaient être remis en question ni par les conclusions retenues à l'issue des stages effectués par l'assuré en 2004, ni par celles du docteur A._ (jugement, consid. 7 p. 24 s.). Il y avait lieu de retenir une baisse de rendement de 10 % (jugement, consid. 8 p. 26) ainsi qu'un abattement sur le salaire statistique déterminant de 10 % (jugement, consid. 9 p. 27). Compte tenu de ces éléments, le taux d'invalidité était de 37 %, insuffisant pour ouvrir le droit à une rente d'invalidité (jugement, consid. 9 p. 27). A partir de juin 2010, en raison de l'atteinte cardiaque de l'assuré combinée à son trouble articulaire, la diminution de rendement était de 20 %; en outre un abattement de 25 % était justifié, si bien que le taux d'invalidité de l'assuré était de 50,53 %, lui ouvrant le droit à une demi-rente (jugement, consid. 9 p. 27 s.).
5. 5.1 L'assuré se plaint d'une constatation arbitraire des faits et d'une violation du droit fédéral. En 1995 déjà, le SMR aurait reconnu que sa capacité de travail ne dépassait pas 50 %, et son état de santé se serait dégradé entre 1999 et 2002. Les responsables du Centre X._, tout comme le docteur A._, auraient exclu l'exercice d'une activité à plein temps. De plus, ni l'OAI, ni les premiers juges n'auraient donné d'exemple concret d'une activité qu'il aurait raisonnablement pu accomplir. En tout état de cause, compte tenu de son âge et de ses limitations fonctionnelles, un abattement de 15 % aurait dû être retenu, dont il découlerait un taux d'invalidité de 45,6 %, lui ouvrant le droit à un quart de rente à compter de janvier 2002. A partir de juin 2010, il n'aurait plus été en mesure de mettre en valeur sa capacité résiduelle de travail, si bien qu'il aurait présenté une invalidité totale, lui donnant droit à une rente entière.
5.2 De son côté, l'OAI se plaint d'une violation du droit fédéral. Les premiers juges n'auraient pas été habilités à prendre en considération les conséquences de l'atteinte cardiaque de l'assuré, celle-ci étant survenue postérieurement à sa décision. Du reste, en dépit de la dégradation de l'état de santé de l'assuré, son taux d'invalidité à partir de juin 2010 serait insuffisant pour lui ouvrir le droit à une rente.
6. L'étendue de l'abattement opéré par la juridiction cantonale sur le salaire avec invalidité résultant des statistiques ESS dans un cas concret constitue une question relevant du pouvoir d'appréciation, qui est soumise à l'examen du juge de dernière instance uniquement si la juridiction cantonale a exercé son pouvoir d'appréciation de manière contraire au droit, soit a commis un excès positif ("Ermessensüberschreitung") ou négatif ("Ermessensunter-schreitung") de son pouvoir d'appréciation ou a abusé ("Ermessensmissbrauch") de celui-ci (<ref-ruling> consid. 5.1 p. 72 s., 132 V 393 consid. 3.3 p. 399).
Il y a abus du pouvoir d'appréciation lorsque l'autorité, tout en restant dans les limites du pouvoir d'appréciation qui est le sien, se fonde sur des considérations qui manquent de pertinence et sont étrangères au but visé par les dispositions légales applicables, ou viole des principes généraux du droit tels que l'interdiction de l'arbitraire et de l'inégalité de traitement, le principe de la bonne foi et le principe de la proportionnalité (<ref-ruling> consid. 2 p. 152 et les références). Commet un excès positif de son pouvoir d'appréciation, l'autorité qui exerce son appréciation alors que la loi l'exclut, ou qui, au lieu de choisir entre les deux solutions possibles, en adopte une troisième. Il y a également excès du pouvoir d'appréciation dans le cas où l'excès de pouvoir est négatif, soit lorsque l'autorité considère qu'elle est liée, alors que la loi l'autorise à statuer selon son appréciation, ou qu'elle renonce d'emblée en tout ou partie à exercer son pouvoir d'appréciation (<ref-ruling> consid. 5.1 p. 73, 116 V 307 consid. 2 p. 310 et les références).
7. 7.1 L'argumentation de l'assuré n'est pas propre à démontrer que l'étendue de sa capacité de travail dans une activité adaptée aurait été établie de façon manifestement inexacte, insoutenable voire arbitraire. Le taux de 50 % retenu par le médecin du SMR, dont il se prévaut, se rapporte à l'activité habituelle, et non à une activité adaptée. Il n'oppose pas d'arguments spécifiques au raisonnement tenu par l'instance cantonale pour privilégier les conclusions des docteurs D._, H._, S._, C._ et P._ par rapport à celles des responsables du Centre X._ et du docteur A._. Le fait que ni l'OAI, ni les premiers juges n'ont cité d'exemple d'activité adaptée ne saurait remettre en cause l'appréciation concordante des médecins précités.
7.2 L'instance cantonale n'a pas non plus commis d'excès ou d'abus de son pouvoir d'appréciation en retenant, pour établir le degré d'invalidité de l'assuré en 2002, un abattement de 10 %. En effet, les limitations fonctionnelles liées au handicap de l'assuré, peu nombreuses, ne sont pas totalement limitatives en l'occurrence (seuls le port de charges, certains mouvements répétitifs et les activités au-dessus de l'horizontale avec le membre supérieur gauche étant exclus) et son âge (52 ans) était relativement éloigné du seuil à partir duquel le Tribunal fédéral parle d'âge avancé (cf. notamment arrêt 9C_612/2007 du 14 juillet 2008 consid. 5.2 et les références).
7.3 C'est à tort que les premiers juges ont alloué à l'assuré une demi-rente d'invalidité à compter du 1er septembre 2010. Même à admettre, comme ils l'ont fait, que son trouble cardiaque existait déjà de manière latente avant juin 2010, il ressort du rapport du docteur O._ que c'est bien à ce moment-là que cette affection a provoqué une diminution de rendement. Or, compte tenu que le juge apprécie en règle générale la légalité des décisions entreprises d'après l'état de fait existant au moment où la décision litigieuse a été rendue (<ref-ruling> consid. 1.2 p. 4 et les arrêts cités, 121 V 362 consid. 1b p. 366), l'instance cantonale n'était pas fondée à octroyer à l'assuré des prestations en se basant sur des circonstances postérieures au 18 février 2010. Ces dernières auraient pu le cas échéant justifier une nouvelle demande. Au cas où l'assuré n'aurait pas entrepris une telle démarche, les pièces qu'il a produites en procédures cantonale et fédérale sur la situation postérieure à la décision administrative pourront être considérées comme une nouvelle demande sur laquelle il appartiendra à l'administration de statuer.
8. Il suit de ce qui précède que le recours de l'Office cantonal genevois de l'assurance-invalidité est bien fondé et celui de l'assuré mal fondé. Ce dernier, qui succombe, doit supporter les frais judiciaires afférents à la présente procédure (cf. <ref-law>).
Compte tenu que l'assuré émarge à l'aide sociale et que ses conclusions ne paraissaient pas d'emblée dépourvues de chances de succès, les conditions d'octroi de l'assistance judiciaire gratuite sont réalisées (art. 64 al. 1 et 2 LTF). L'attention de l'assuré est attirée sur le fait qu'il devra rembourser la caisse du Tribunal fédéral s'il devient en mesure de le faire ultérieurement (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Les causes 9C_466/2011 et 9C_432/2011 sont jointes.
2. Le recours de l'Office cantonal genevois de l'assurance-invalidité est admis, le jugement de la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, du 3 mai 2011, étant annulé.
3. Le recours de M._ est rejeté.
4. La demande d'assistance judiciaire de M._ est admise. Me Christian Fischele est désigné comme avocat d'office.
5. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de l'assuré. Il sont toutefois supportés provisoirement par la caisse du Tribunal.
6. Une indemnité de 2'800 fr., provisoirement supportée par la caisse du Tribunal, est allouée à Me Fischele à titre d'honoraires.
7. Le présent arrêt est communiqué aux parties, à la Cour de justice de la République et canton de Genève, Chambre des assurances sociales, et à l'Office fédéral des assurances sociales.
Lucerne, le 15 novembre 2011
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: Meyer
Le Greffier: Bouverat