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. 