Faits:
A. M._, né en 1948, sans formation professionnelle, travaille comme épicier à titre indépendant depuis 1981. Dès le 2 août 2001, il a été en incapacité de travail à 50 %. Le 21 octobre 2002, il a déposé une demande de prestations de l'assurance-invalidité tendant à l'octroi d'une rente.
Dans un rapport du 29 octobre 2002, le docteur G._, du Service de rhumatologie de l'Hôpital X._, a posé le diagnostic d'arthrose à localisations multiples (rachis, genou droit et les deux épaules) plus marquée à droite, coxarthrose gauche débutante non exclue et obésité (BMI 34). Le 5 novembre 2002, le docteur R._, médecin traitant de l'assuré, a fait état de polyarthralgies à focalisation rachidienne et cervico-scapulaire et de gonarthrose droite depuis août 2001. La comparaison des champs d'activités issue du rapport d'enquête pour les indépendants du 14 janvier 2004 a abouti à une limitation globale de 50 %; quant aux incapacités de travail, elles ont généré, en prenant en compte le salaire théorique pour chacune de ces activités (ventes, livraisons et gestion), un taux d'invalidité de 52,33 %.
L'Office de l'assurance-invalidité pour le canton de Vaud (ci-après: l'office AI) a chargé le docteur T._, spécialiste FMH en rhumatologie et médecine interne, d'une expertise. Dans un rapport du 5 avril 2004, ce médecin a fait état de rachialgies chroniques et polyarthralgies prédominant à l'épaule droite et au genou droit, troubles statiques et dégénératifs modérés du rachis, gonarthrose et omarthrose droite, psoriasis cutané et de lichen plan généralisé. La capacité de travail était évaluée à 50 % dans l'activité habituelle d'épicier depuis le mois d'août 2001 mais pouvait atteindre 85 % dans une activité professionnelle légère sans mouvements répétitifs en porte-à-faux du rachis, travaux lourds, ports de charges de plus de 15 kilos, marche prolongée, principalement la montée et la descente des escaliers et mouvements répétitifs du membre supérieur droit.
Dans un rapport du 16 juin 2005, le docteur G._ a estimé que la demande de rente était justifiée par les handicaps que rencontrait l'assuré dans son activité d'épicier indépendant, qui limitaient ses capacités de charge. Il a indiqué que l'assuré travaillait en réalité au-delà de ses forces et qu'un taux d'activité de 50 % était le maximum exigible.
Par décision du 27 mars 2006, confirmée sur opposition le 24 janvier 2008, l'office AI a nié le droit de l'assuré à une rente d'invalidité. Il a considéré que ce dernier présentait une capacité de travail de 85 % dans une activité adaptée à son état de santé, lui permettant de réaliser un revenu de 41'188 fr. 33, supérieur au revenu sans invalidité de 26'635 fr. qu'il était en mesure de prétendre dans son activité d'épicier indépendant, de sorte qu'il ne subissait pas de préjudice économique.
B. M._ ayant formé un recours contre la décision du 24 janvier 2008, la Cour des assurances sociales du Tribunal cantonal vaudois l'a partiellement admis, par jugement du 3 novembre 2009. La juridiction cantonale a réformé la décision entreprise, accordant à M._ une demi-rente d'invalidité depuis le 1er août 2002.
C. L'office AI interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation, concluant à la confirmation de sa décision.
Statuant sur une demande de M._ visant à l'octroi de l'assistance judiciaire gratuite et à la désignation de Me Hofstetter comme avocat d'office, le Tribunal fédéral l'a admise par ordonnance du 10 mars 2010.
M._ 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 (<ref-law>) peut être formé pour violation du droit selon l'art. 95 sv. LTF. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>) et peut rectifier ou compléter d'office les constatations de celle-ci si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>).
2. Le litige porte sur le droit de l'intimé à une rente d'invalidité. A cet égard, le jugement entrepris expose correctement les normes légales sur la notion d'invalidité et son évaluation. Il suffit d'y renvoyer.
3. L'office recourant estime que la juridiction cantonale a violé le droit fédéral en n'appliquant pas, dans le cas d'espèce, la méthode générale de comparaison des revenus pour fixer le degré d'invalidité de l'assuré. Pour continuer à exercer son activité habituelle d'épicier malgré ses limitations fonctionnelles, l'intimé avait dû réorganiser celle-ci en diminuant son temps de travail et en réaménageant ses activités, ce qui pouvait avoir des répercussions sur son chiffre d'affaires. Compte tenu de ces modifications, le revenu d'invalide de l'intimé ne correspondait pas à la moitié de son revenu sans invalidité, comme l'avaient retenu les premiers juges. Le recourant reproche ensuite à la juridiction cantonale d'avoir établi les faits de façon manifestement inexacte en s'écartant des conclusions claires et bien motivées de l'expert T._, selon lesquelles l'intimé pouvait encore exercer une activité adaptée à 85 %. En retenant que l'exercice de son activité d'épicier au taux de 50 % était le maximum que l'on pouvait exiger de l'intimé, la juridiction cantonale avait au demeurant fait totalement abstraction du principe de l'obligation de réduire le dommage.
4. L'autorité judiciaire de première instance a constaté que l'intimé conservait une capacité résiduelle de travail de 50 % dans son activité habituelle d'épicier, compte tenu d'une adaptation de son poste de travail à ses limitations fonctionnelles (réduction des horaires d'ouverture de l'épicerie, suppression des livraisons à domicile). Quant à une éventuelle capacité résiduelle de travail de l'intimé dans une activité adaptée à ses limitations fonctionnelles, la juridiction cantonale a considéré que l'office AI ne décrivait pas quelle pouvait être cette activité. Quoi qu'il en soit, le docteur G._, qui avait reconnu dans un premier temps qu'une activité légère permettant l'alternance des postures et évitant tout mouvement des épaules au-dessus de l'horizontale était théoriquement envisageable (cf. rapport du 28 octobre 2002), affirmait dans son rapport du 16 juin 2005 qu'un taux de 50 % restait le maximum exigible. Or, procéder à un complément d'instruction en demandant à l'office AI d'énumérer un certain nombre d'activités correspondant aux limitations fonctionnelles retenues s'avérait superflu puisque l'activité d'épicier exercée à 50 % apparaissait judicieuse, tant du point de vue du handicap de l'intimé que de celui de son manque de qualifications professionnelles. En tant que la juridiction cantonale s'est prononcée sur l'exigibilité de la mise en valeur de la capacité de travail de l'intimé, il s'agit d'une constatation de fait (<ref-ruling> consid. 3.2 p. 398) qui n'apparaît pas manifestement inexacte ni contraire au droit. Il n'y a dès lors pas lieu de revenir sur la constatation des premiers juges, selon laquelle on ne saurait attendre de l'intimé qu'il change d'activité, celle d'épicier étant suffisamment adaptée.
5. 5.1 En ce qui concerne les répercussions économiques de l'incapacité de travail de l'intimé, les premiers juges ont simplement mentionné que le taux d'invalidité se confondait avec celui de l'incapacité de travail, sans préciser si l'invalidité devait être évaluée selon la méthode d'évaluation dite extraordinaire ou selon la méthode ordinaire dite de comparaison des revenus. Conformément à la jurisprudence exposée dans le jugement entrepris (consid. 3b; <ref-ruling> consid. 1 p. 30), on rappellera que la méthode extraordinaire de l'évaluation de l'invalidité doit être appliquée lorsqu'il n'est pas possible d'établir ou d'évaluer de manière fiable les deux revenus hypothétiques provenant d'une activité lucrative.
5.2 En l'espèce, il ressort des constatations des premiers juges que l'intimé avait adapté son poste de travail à son handicap, de sorte qu'il pouvait rester assis le 90 % de son temps et se mouvoir à sa guise; il ne faisait que servir les clients et disposer la marchandise sur les rayons, sans pour autant effectuer certains rangements en hauteur. Sur la base de ces renseignements issus du rapport d'enquête économique pour les indépendants du 14 janvier 2004, l'office AI avait considéré devoir appliquer la méthode extraordinaire d'évaluation de l'invalidité mais avait en réalité effectué une comparaison des revenus selon la méthode ordinaire d'évaluation, tout en recourant à des éléments relevant de la comparaison des champs d'activités. Une telle manière de procéder ne correspond pas aux modalités de calcul de la méthode extraordinaire (cf. <ref-ruling> consid. 4c p. 33). Si les premiers juges entendaient faire application de cette méthode de calcul qui n'a finalement pas été retenue par l'office AI, il leur appartenait d'établir les faits relatifs à la pondération des champs d'activité de l'intimé, à l'étendue de l'empêchement entraîné par les atteintes à la santé sur chacun des champs d'activité ainsi qu'aux revenus à prendre en considération. Vu l'établissement lacunaire des faits par la juridiction cantonale et l'application erronée de la méthode d'évaluation extraordinaire de l'invalidité par l'administration, il convient d'annuler le jugement de la Cour des assurances sociales du Tribunal cantonal et de lui renvoyer la cause pour qu'elle procède à la fixation du taux d'invalidité en application des règles propres à la méthode extraordinaire, compte tenu de la capacité de travail réduite de l'intimé dans sa profession (au moyen de la formule d'évaluation dans l'<ref-ruling> consid. 4c p. 33; cf. aussi l'arrêt 9C_731/2007 du 20 août 2008 consid. 5).
6. Compte tenu de l'issue du litige, les frais de justice sont répartis par moitié entre les parties (<ref-law>). L'intimé, représenté par un avocat, a droit à une indemnité de dépens réduite à la charge de l'office recourant pour la procédure fédérale (<ref-law>).
L'intimé a demandé à bénéficier de l'assistance judiciaire pour la procédure fédérale qui lui a été accordée par ordonnance du 10 mars 2010. Son attention 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. Le recours est partiellement admis, l'arrêt entrepris annulé et la cause renvoyée à la cour cantonale pour nouvelle décision au sens des considérants.
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'intimé. La caisse du tribunal supportera provisoirement, au titre des frais de justice couverts par l'assistance judiciaire, un montant de 250 fr. en faveur de l'intimé.
3. Le recourant versera à l'intimé la somme de 700 fr. à titre de dépens pour la dernière instance. Une indemnité de 700 fr., supportée provisoirement par la caisse du tribunal est allouée à Me Hofstetter à titre d'honoraires non couverts par l'indemnité de dépens.
4. Le présent arrêt est communiqué aux parties, à la Cour des assurances sociales du Tribunal cantonal vaudois et à l'Office fédéral des assurances sociales.
Lucerne, le 20 octobre 2010
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Meyer Fretz Perrin