Faits:
A. S._ a travaillé en qualité de maçon. Victime d'un accident professionnel sur un chantier le 25 octobre 2004, il a subi une déchirure de la coiffe des rotateurs de l'épaule droite, qui a été traitée par une acromioplastie. Il a été mis en arrêt de travail et a présenté une demande de prestations de l'assurance-invalidité le 5 avril 2005. Une expertise sollicitée par la Caisse nationale suisse d'assurance en cas d'accidents (CNA) a été menée par les docteurs M._, B._ et Z._ de la Clinique et Polycliniques de rhumatologie et immunologie clinique/allergologie de l'Hôpital X._. Ceux-ci ont conclu à l'incapacité de travail totale de l'assuré dans la profession de maçon et à une capacité de travail entière dans une activité légère à moyennement lourde (rapport du 20 juin 2007). Par décision du 29 octobre 2007, l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-après: office AI) a refusé d'octroyer une rente à l'assuré, dès lors qu'il pouvait exercer une activité adaptée à plein temps et que son taux d'invalidité était inférieur à 40 %. Cette décision a été annulée pour violation du droit d'être entendu de l'assuré par arrêt du 18 mars 2008 du Tribunal administratif de la République et canton de Neuchâtel, Cour des assurances sociales, qui a renvoyé la cause à l'administration pour qu'elle fasse traduire le rapport des médecins de l'Hôpital X._ en français et donne l'occasion à l'intéressé de se prononcer. Dans ses observations du 18 août 2008, l'assuré a notamment requis de l'office AI qu'il pose deux questions complémentaires aux experts de l'Hôpital X._.
Par la suite, l'intéressé a déposé une expertise du 28 novembre 2008 du docteur L._ qui retenait une incapacité de travail totale dans toute profession. S'écartant de ces conclusions, l'office AI a rejeté à nouveau la demande de rente par décision du 12 février 2009.
B. L'assuré a déféré cette décision au Tribunal administratif de la République et canton de Neuchâtel, Cour des assurances sociales, qui l'a débouté par jugement du 6 mai 2010.
C. S._ interjette un recours en matière de droit public contre ce jugement, dont il demande l'annulation. Sous suite de frais et dépens, il conclut en substance à la reconnaissance de son droit à une rente d'invalidité et, subsidiairement, au renvoi de la cause à la juridiction cantonale, voire à l'office AI, pour instruction complémentaire et nouvelle décision. Il sollicite, par ailleurs, le bénéfice de l'assistance judiciaire.
L'office AI conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer.
Considérant en droit:
1. Le recours en matière de droit public (art. 82 ss LTF) peut être formé pour violation du droit au sens des art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF), n'examine en principe que les griefs invoqués (art. 42 al. 2 LTF) et fonde son raisonnement sur les faits retenus par la juridiction de première instance (art. 105 al. 1 LTF), sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF auquel cas il peut les rectifier ou les compléter d'office (art. 105 al. 2 LTF).
2. Le litige porte sur le droit du recourant à une rente d'invalidité. Le jugement attaqué expose correctement les règles légales et la jurisprudence qui sont applicables en l'espèce, si bien qu'il suffit d'y renvoyer.
3. Pour apprécier la capacité de travail résiduelle du recourant et par conséquent son taux d'invalidité, la juridiction cantonale s'est basée sur les conclusions des experts de l'Hôpital X._. Après avoir détecté un soupçon d'amplification des symptômes, les experts ont considéré qu'en faisant un bon effort, le recourant pouvait fournir nettement plus que ce qu'il avait montré lors des tests. Un travail de pénibilité moyenne était donc exigible au prix de certaines limitations relatives au port de charge (maximum 22,5 kg pour le port de charge unilatéral de la main gauche), aux travaux au-dessus du niveau de la tête, à la force manuelle, à la coordination des mains et aux actions de ramper, tirer et pousser. Accordant pleine valeur probante à cette expertise, dès lors qu'elle tenait compte des plaintes du patient, se fondait sur une anamnèse complète, sur les résultats des examens clinique et médicographique, ainsi que sur l'évaluation des performances fonctionnelles, la juridiction cantonale a alors retenu que le recourant disposait d'une pleine capacité de travail dans des activités légères à moyennes respectant les limitations fonctionnelles décrites par les experts. Dans la mesure où le taux d'invalidité était insuffisant pour ouvrir le droit à une rente, les premiers juges ont refusé d'octroyer cette prestation à l'assuré. Ils ont, par ailleurs, écarté l'expertise du docteur L._ qui constatait que l'intéressé ne pouvait plus reprendre d'activité professionnelle, même adaptée.
4. 4.1 Dans un premier grief, le recourant se plaint de n'avoir pas eu le droit à l'assistance d'un interprète durant toute la durée de l'expertise qui s'est déroulée sur trois jours à l'Hôpital X._, l'interprète désigné n'ayant été présent que lors de la première journée. Vu son niveau insuffisant en français, il n'aurait pas pu exposer correctement ses plaintes et les difficultés rencontrées lors des tests.
4.1.1 La réalisation d'une expertise exige que l'expert et l'assuré se comprennent. Il n'est cependant pas nécessaire que cette compréhension soit totale; il suffit que le praticien puisse recueillir les éléments utiles à une appréciation fidèle et pertinente de la situation (arrêt 9C_1040/2008 du 17 avril 2009 consid. 2). Dans le cadre d'un examen somatique, on ne peut pas parler a priori d'une violation du droit d'être entendu lorsque malgré des difficultés de compréhension une expertise ne se déroule pas dans la langue maternelle de l'assuré et qu'aucun interprète n'est présent. La question de savoir si dans un cas concret un examen médical doit se dérouler dans la langue maternelle de l'assuré ou avec l'assistance d'un interprète, est en principe laissée à la libre appréciation de l'expert, responsable de la bonne exécution de son mandat (arrêt I 748/03 du 3 mars 2004 consid. 2.1).
4.1.2 En l'espèce, il ressort du rapport d'expertise que le recourant a compris les questions posées par les docteurs M._, B._ et Z._ et que ces derniers ont bien saisi ses réponses. Ils sont parvenus à établir une anamnèse complète pour se prononcer et à retranscrire les plaintes du patient. Les tests destinés à évaluer la performance fonctionnelle de l'intéressé ont été réalisés sans problème et les résultats ne paraissent pas avoir été faussés par une mauvaise compréhension entre les protagonistes, ce que ne démontre par ailleurs pas le recourant au moyen d'exemples concrets. Les médecins n'ont pas renoncé à terminer l'expertise sans la présence d'un interprète lors des deux dernières journées: on peut en déduire qu'ils ont estimé suffisant le niveau de compréhension de la langue de l'assuré. Le grief du recourant doit dès lors être rejeté.
4.2 S._ reproche aux mêmes experts de ne pas s'être prononcés sur les avis de ses médecins traitants. Toutefois, dans la première partie de leur évaluation, ces spécialistes ont cité l'ensemble des avis médicaux se trouvant au dossier (y compris diagnostics et conclusions), dont ils ont ensuite tenu compte dans leur appréciation. Cette manière de procéder a permis de dresser le contexte médical et d'évaluer la situation médicale du recourant de façon satisfaisante. C'est donc à juste titre que les premiers juges ont retenu que l'expertise de l'Hôpital X._ répondait aux critères dégagés par la jurisprudence en matière de valeur probante (cf. ATF 125 V 351 consid. 3a p. 352; 122 V 157 consid. 1c p. 160 et les références).
4.3 Toujours d'après le recourant, cette expertise comporte en outre des contradictions. Selon lui, il existe un décalage entre les limitations fonctionnelles retenues par les experts et l'évaluation qu'ils en ont faite pour déterminer l'activité exigible. Il soutient que les médecins de l'Hôpital X._ ont omis de signaler qu'il ne pouvait pas utiliser son bras droit, même pour des tâches manuelles, ni à titre de support et qu'il ne pouvait réaliser avec sa main gauche des travaux fins et légers qui lui permettraient d'accéder au marché du travail. Ce faisant, sans étayer ses allégations sur la base de données médicales objectives, il ne fait que substituer sa propre appréciation sur son état de santé et ses limitations fonctionnelles à celle des médecins dont l'avis a été suivi par les juges cantonaux. Son grief est dès lors insuffisant pour remettre en cause la valeur probante de l'expertise en ce qu'elle serait contradictoire.
4.4 Le recourant invoque également une violation de son droit d'être entendu, en tant que l'office AI a rendu sa décision sans donner suite à sa requête du 18 août 2008 qui visait à poser deux questions complémentaires aux experts de l'Hôpital X._.
4.4.1 La violation invoquée par le recourant, qui concerne en réalité la valeur probante de l'expertise, n'a pas de portée propre par rapport au grief tiré d'une mauvaise appréciation des preuves (cf. ATF 130 II 425 consid. 2.1 p. 429). Le juge - l'administration dans ce cas - peut en effet renoncer à accomplir certains actes d'instruction si, en se fondant sur une appréciation consciencieuse des preuves, il est convaincu que certains faits présentent un degré de vraisemblance prépondérante et que d'autres mesures probatoires ne pourraient plus modifier son appréciation (cf. ATF 135 V 465 consid. 4.3.2 p. 469; 134 I 140 consid. 5.3 p. 148; 131 I 153 consid. 3 p. 157).
4.4.2 En l'occurrence, on constate que l'intimé n'a pas fait une appréciation (anticipée) arbitraire des preuves en refusant de procéder au complément d'instruction requis. Les questions que le recourant entendait poser aux experts de l'Hôpital X._ étaient dénuées de pertinence. La première question portait sur la détermination de l'activité professionnelle légère à moyennement lourde que l'on pouvait exiger de lui compte tenu de sa situation personnelle et de ses aptitudes physiques, tandis que la seconde question concernait la notion du travail de pénibilité moyenne. En se référant au Dictionary of Occupational Titles [DOT], les experts ont défini le "travail de pénibilité moyenne" par une limitation du port de charge de 15 à 25 kg. Concernant la première question, les mêmes experts ont décrit les limitations fonctionnelles qu'il fallait prendre en considération dans le cas du recourant pour définir une activité de pénibilité moyenne adaptée. Une nouvelle prise de position de leur part sur ces questions n'était donc pas indispensable pour trancher le litige et c'est à bon droit que les premiers juges n'ont pas retenu le grief du recourant sur ce point.
5. Dans une autre série de motifs, le recourant remet en cause le bien-fondé des conclusions de l'expertise de l'Hôpital X._ qui seraient contredites avant tout par l'avis du docteur L._, mais également par l'évaluation du conseiller en réadaptation professionnelle de l'intimé (rapport du 17 août 2006).
5.1 En présence d'avis contradictoires, le juge doit apprécier l'ensemble des preuves à disposition et indiquer les motifs pour lesquels il se fonde sur une appréciation plutôt qu'une autre. Une évaluation médicale complète ne saurait toutefois être remise en cause pour le seul motif qu'un ou plusieurs médecins ont une opinion divergente. Pour qu'il en aille différemment, il appartient à la partie recourante de mettre en évidence des éléments objectivement vérifiables - de nature notamment clinique ou diagnostique - qui auraient été ignorés dans le cadre de l'appréciation et qui seraient suffisamment pertinents pour remettre en cause le bien-fondé du point de vue sur lequel se sont fondés les premiers juges ou établir le caractère incomplet de celui-ci (arrêt 9C_578/2009 du 29 décembre 2009 consid. 3.2). Compte tenu de son pouvoir d'examen restreint (supra consid. 1), il n'appartient pas au Tribunal fédéral de procéder une nouvelle fois à l'appréciation des preuves administrées, mais à la partie recourante d'établir en quoi celle opérée par l'autorité cantonale serait insoutenable, ou en quoi les faits constatés seraient manifestement inexacts ou incomplets ou auraient été établis en violation du droit.
5.2 Les premiers juges ont expliqué les raisons pour lesquelles ils suivaient les conclusions des experts de l'Hôpital X._ et s'écartaient de l'appréciation du docteur L._. D'après eux, ce spécialiste a négligé que les limitations fonctionnelles du recourant ne concernaient que le membre supérieur droit et qu'il existait un bon nombre d'activités simples et répétitives qui permettaient d'épargner l'épaule au-delà de ce qui était exigible. En l'occurrence, la motivation du recourant consiste essentiellement à souligner la divergence d'opinion entre le collège d'experts et le docteur L._ quant aux limitations fonctionnelles retenues et au degré de capacité de travail exigible qui s'ensuit. Le recourant n'apporte aucun élément objectivement vérifiable qui ressortirait de son dossier médical et qui aurait été ignoré des premiers juges. En particulier, il ne démontre pas en quoi le point de vue du docteur L._ serait objectivement mieux fondé que celui des experts ou justifierait la mise en oeuvre d'une instruction complémentaire. Le fait que ce médecin soit d'une opinion différente concernant la capacité de travail résiduelle du recourant eu égard aux limitations fonctionnelles qu'il retient (utilisation maximale du membre supérieur de 30 minutes et port de charges maximal de 1kg) ne suffit pas à remettre en cause les conclusions des experts de l'Hôpital X._. En effet, ce praticien ne met en évidence aucun élément médical qui aurait été ignoré par les médecins de l'Hôpital X._. Dans une large mesure, il reprend le même diagnostic que les experts, ainsi que les mêmes limitations fonctionnelles, mais parvient à des conclusions différentes quant à la capacité de travail de l'intéressé dans une activité adaptée. Il ne prend pas position sur les conclusions de ses confrères, si ce n'est en faisant état d'une aggravation de l'état de santé de l'assuré, sans toutefois la motiver réellement. Enfin, l'argument du recourant, selon lequel l'expertise du docteur L._ est plus récente, n'est pas pertinent, l'écoulement du temps n'altérant pas à lui seul la valeur probante d'une expertise (arrêt 9C_351/2010 du 17 décembre 2010 consid. 4.2).
En conséquence, il n'y a pas lieu de douter du bien-fondé de l'expertise de l'Hôpital X._ et partant du résultat de l'appréciation des preuves opérée par la juridiction cantonale. Dès lors que l'expertise du docteur L._ n'était pas propre à remettre en cause celle de l'Hôpital X._, il n'était pas non plus nécessaire de faire une instruction complémentaire contrairement à ce que prétend le recourant.
5.3 Le recourant soutient encore que la juridiction cantonale aurait écarté à tort le rapport de la réadaptation professionnelle du 17 août 2006, car il était antérieur à l'expertise de l'Hôpital X._. L'argumentation de la juridiction précédente est toutefois sensiblement différente, puisqu'elle n'a pas suivi les conclusions du conseiller en réadaptation professionnelle aux motifs qu'elles ne reposaient que sur deux tests d'habileté manuelle et qu'elles ne tenaient pas compte de la nette auto-limitation observée postérieurement chez le recourant par les experts de l'Hôpital X._. En reprochant à tort à la juridiction précédente d'avoir écarté le rapport de la réadaptation professionnelle pour des motifs temporels, le recourant ne démontre pas à satisfaction de droit que l'appréciation des preuves, en tant qu'elle conduit à écarter le rapport, serait arbitraire.
5.4 Contrairement à ce que soutient ensuite le recourant, une instruction complémentaire n'était pas non plus nécessaire sur le plan psychique. A l'appui de son argumentation, le recourant se fonde sur l'expertise de l'Hôpital X._ qui préconisait la clarification de son état psychosomatique et sur l'avis du docteur L._ qui a constaté un état dépressif lié à une déchéance physique consécutive à l'accident. A l'instar des premiers juges, on retient que les experts de l'Hôpital X._ n'ont émis qu'une recommandation à ce sujet à mettre en relation avec l'amplification des symptômes observée et que le docteur L._ a diagnostiqué un état dépressif n'ayant cependant pas de répercussion sur la capacité de travail. En l'absence d'indices médicaux concrets quant à l'existence d'une maladie psychique invalidante, le refus de la juridiction cantonale de procéder à la mesure d'instruction requise n'apparaît pas arbitraire.
5.5 Le recourant ne voit pas très bien quelle activité il pourrait encore exercer vu les limitations fonctionnelles qu'il présente au niveau du membre supérieur droit; il reproche à l'autorité de première instance de ne pas avoir examiné cette question de manière satisfaisante. Se référant à une jurisprudence constante (arrêt 8C_377/2009 du 18 février 2010 consid. 7.1 et les références citées; arrêt I 606/02 du 30 janvier 2003 consid. 3), les premiers juges ont retenu qu'au regard du large éventail d'activités simples que recouvrent les secteurs de la production et des services, un certain nombre d'entre elles étaient adaptées au handicap du recourant. On peut certes regretter que ni l'administration ni la juridiction cantonale n'aient donné d'exemples concrets de l'une ou l'autre des activités exigibles. Toutefois, les premiers juges, qui ont tenu compte des limitations fonctionnelles du recourant, n'ont pas violé le droit fédéral. Il existe effectivement un nombre suffisant de postes compatibles avec les limitations physiques du recourant; on peut citer ici à titre d'exemples les activités de surveillant de machines et de gardien de parking, ou encore les activités d'accueil.
6. En conséquence de ce qui précède, les griefs du recourant apparaissent en tous points mal fondés et ses conclusions doivent être rejetées.
7. Vu l'issue du litige, le recourant qui succombe devrait en principe supporter les frais judiciaires (art. 66 al. 1 LTF). Toutefois, comme celui-ci satisfait aux conditions de l'art. 64 al. 1 LTF, il est dispensé de l'obligation de payer les frais judiciaires. Quant aux conditions auxquelles l'art. 64 al. 2 LTF subordonne la désignation d'un avocat d'office, elles sont également réalisées. L'attention du recourant est cependant attirée sur le fait qu'il devra rembourser la caisse du tribunal s'il devient en mesure de le faire ultérieurement (art. 64 al. 4 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. L'assistance judiciaire est accordée au recourant.
3. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant. Ils sont toutefois supportés provisoirement par la caisse du Tribunal.
4. Me Ana Duran est désignée en tant qu'avocate d'office du recourant et une indemnité de 2'800 fr. lui est allouée à titre d'honoraires, supportée par la caisse du Tribunal.
5. Le présent arrêt est communiqué aux parties, au Tribunal administratif de la République et canton de Neuchâtel, Cour des assurances sociales, et à l'Office fédéral des assurances sociales.
Lucerne, le 4 février 2011
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Meyer Reichen