Faits:
A. M._ appartient à la communauté des gens du voyage. Il a exercé les activités de rémouleur, de réparateur de parapluies et de brocanteur. Le 29 octobre 2003, il a déposé une demande de rente de l'assurance-invalidité. Dans le cadre de l'instruction du cas, l'office de l'assurance-invalidité (ci-après: l'OAI) a notamment confié un mandat d'expertise psychiatrique au docteur E._ (rapport du 7 janvier 2005), selon laquelle l'assuré était atteint d'un état dépressif majeur de gravité légère à moyenne et de claustrophobie avec agoraphobie de gravité légère, ces affections conduisant à une diminution de sa capacité de travail de plus de 30 %. Par décision du 11 février 2005, la demande de prestations a été rejetée; l'OAI l'a confirmée sur opposition le 11 juillet 2008, après avoir mis en oeuvre une nouvelle expertise psychiatrique confiée au docteur A._, établie le 7 avril 2008.
B. M._ a formé recours contre cette dernière décision, dans lequel il a conclu à son annulation en mettant en cause la valeur probante des expertises mises en oeuvre par l'administration. Il a fait valoir qu'il est incapable d'exercer seul une activité professionnelle et a contesté pouvoir se faire accompagner toujours par son père ou des proches. Il a ainsi demandé qu'il soit procédé à une nouvelle expertise, de préférence en allemand et par des psychiatres qui n'ont pas de préjugés au sujet des gens du voyage. Le Tribunal administratif, Cour des assurances sociales, de la République et canton de Neuchâtel a rejeté le recours par jugement du 22 décembre 2008.
C. M._ interjette un recours en matière de droit public contre ce jugement et conclut, sous suite de frais et dépens, à l'octroi d'une demi-rente d'invalidité.
D. Le juge chargé de l'instruction de la présente affaire a recueilli des renseignements supplémentaires dans le cadre de la procédure probatoire, en soumettant un questionnaire au docteur A._. Ses réponses du 9 juillet 2009 ont été communiquées aux parties. Le recourant s'est déterminé par réponse du 14 octobre 2009.
L'OAI 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. 1.1 Le recours en matière de droit public (<ref-law>) peut être formé pour violation du droit selon les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours ni par la motivation retenue par l'autorité précédente ; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 1.4 p. 140). Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il peut cependant rectifier ou compléter d'office les constatations de l'autorité précédente si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>).
1.2 Le litige porte sur le droit de l'assuré à une rente d'invalidité, le recourant faisant valoir qu'en lui refusant cette prestation, l'autorité judiciaire de première instance a établi les faits de façon manifestement inexacte, a violé le droit fédéral et a procédé à une appréciation arbitraire des preuves. Dans le jugement entrepris, le Tribunal cantonal a exposé les dispositions légales et réglementaires ainsi que les principes de jurisprudence applicables en l'espèce, de sorte qu'il suffit d'y renvoyer.
2. 2.1 Pour refuser le droit à une rente d'invalidité, le Tribunal cantonal s'est notamment fondé sur l'expertise psychiatrique du docteur A._ (rapport du 7 avril 2008), à laquelle il a reconnu pleine valeur probante. Les premiers juges ont considéré que les arguments du recourant ne sont pas fondés dans la mesure où il conteste les conclusions du docteur A._. Selon l'expert psychiatre une capacité de travail entière est donnée en tenant compte de l'accompagnement de l'assuré par un proche pour se rendre chez les clients potentiels. Les juges cantonaux ont relevé que selon le docteur A._, l'assuré travaille à tout le moins l'après-midi et que l'expérience de la vie enseigne que les gens du voyage ne se déplacent pas seuls lorsqu'ils proposent leurs services de porte à porte. En distinguant entre le mandat thérapeutique assumé par la doctoresse Y._, psychiatre traitant du recourant, et le mandat d'expertise confié au docteur A._, ils ont en outre considéré qu'il n'y avait pas lieu de compléter l'instruction.
2.2 Le recourant reproche aux juges cantonaux d'avoir déduit de l'expérience de la vie des conclusions inexactes et arbitraires relatives aux gens du voyage, lesquelles ne correspondent nullement aux faits tels qu'ils se présentent dans sa vie personnelle. Il considère que, si selon le docteur A._ il ne travaille que l'après-midi, sa capacité de travail résiduelle ne peut être supérieure à 50 %. Il conteste cependant l'opinion de l'expert dans la mesure où celui-ci affirme qu' il se fait accompagner par son père ou ses proches pour exercer sa profession de rémouleur. A son avis, dès lors qu'il devrait effectivement se faire accompagner par un proche pour se rendre chez les gens afin de leur demander du travail et qu'il est ainsi incapable de travailler seul, une incapacité de travail dans son activité professionnelle doit manifestement être admise.
3. 3.1 Le juge chargé de l'instruction dans la présente affaire a recueilli des renseignements supplémentaires en soumettant au docteur A._ des questions précises. Dans sa réponse du 9 juillet 2009, l'expert a notamment indiqué que c'est sur la base des informations données tant par l'assuré que par son père qu'il était arrivé à la conclusion que le recourant exerçait son activité d'aiguiseur de couteaux et de ciseaux en étant accompagné par son père ou par un autre proche. Il a cependant indiqué, en étant formel sur ce point, que le fait de se faire accompagner par son père ou par un autre proche ne constitue absolument pas une condition indispensable pour que l'assuré puisse oeuvrer dans son activité habituelle d'aiguiseur de couteaux et de ciseaux. Il a précisé que, s'il avait considéré que cette condition était indispensable, il en aurait attesté la nécessité, qu'il aurait alors logiquement admis une incapacité de travail psychique et qu'il aurait indiqué que l'assuré ne peut travailler en plein qu'à la condition expresse qu'il soit accompagné par une personne qu'il considère comme sûre, en constatant que cette condition aurait été difficilement exigible en l'espèce.
3.2 Les réponses du docteur A._ sont claires et convaincantes. Elles ne laissent subsister aucun doute sur la capacité de travail du recourant, laquelle est considérée entière aussi selon les nouvelles précisions de l'expert psychiatre et a été évaluée à plus de 60 % par le docteur E._ dans le rapport du 7 janvier 2005. Dans ces conditions, l'argumentation développée par le recourant tant dans son recours que dans sa réponse du 14 octobre 2009 ne démontre pas en quoi la juridiction de première instance se serait fondée sur des faits établis de manière manifestement inexacte, aurait violé le droit fédéral ou aurait procédé à une appréciation arbitraire des preuves. C'est dès lors à juste titre que le Tribunal cantonal a nié le droit de l'assuré à une rente d'invalidité.
4. Le recourant qui succombe, doit en principe supporter les frais judiciaires (art. 66 al. 1 première phrase LTF). Néanmoins, compte tenu des manquements dans la procédure probatoire de première instance, sans lesquels le recours n'aurait probablement pas été interjeté ou ne l'aurait pas été en la présente forme, il se justifie de repartir les frais judiciaires par moitié entre le recourant et l'Office intimé (<ref-law>). Le recourant a droit, en outre, à une indemnité de dépens réduite pour la procédure fédérale (art. 68 al. 4 en relation avec l'<ref-law>)

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis pour 250 fr. à la charge du recourant et pour 250 fr. à la charge de l'Office intimé.
3. L'Office intimé versera au recourant une indemnité de dépens de 1'400 fr. à titre de dépens pour l'instance fédérale.
4. Le présent arrêt est communiqué aux parties, au Tribunal administratif du canton de Neuchâtel et à l'Office fédéral des assurances sociales.
Lucerne, le 26 octobre 2009
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Meyer Scartazzini