Faits:
A. Par décision du 14 janvier 2004, confirmée sur opposition le 22 avril 2004, l'Office cantonal de l'assurance-invalidité du canton de Genève (ci-après: OCAI) a rejeté la demande de prestations déposée par L._, né en 1952, le 27 novembre 2001. La décision sur opposition du 22 avril 2004 est entrée en force, l'assuré ayant retiré le recours qu'il avait interjeté à son encontre le 10 mai 2004.
Le 7 mars 2005, L._ a déposé une nouvelle demande de prestations. Par décision du 26 avril 2005, confirmée sur opposition le 7 juillet 2005, l'OCAI a rejeté la demande, au motif que les conditions permettant une révision, voire même une reconsidération du cas, n'étaient pas remplies, l'état de santé de l'assuré n'ayant subi aucun changement depuis la décision de refus de prestations du 22 avril 2004.
B. L._ a déféré la décision sur opposition du 7 juillet 2005 au Tribunal cantonal des assurances sociales du canton de Genève, en concluant à son annulation et à ce qu'une incapacité de travail de 50 % lui soit reconnue dans une activité adaptée.
Par jugement du 23 novembre 2006, la juridiction cantonale a partiellement admis le recours et alloué à L._ un quart de rente d'invalidité à partir du 1er novembre 2002.
C. L'OCAI interjette un recours en matière de droit public contre ce jugement, dont il requiert l'annulation, en concluant à la confirmation de sa décision sur opposition du 7 juillet 2005.
L'intimé conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a proposé son admission.

Considérant en droit:
1. La loi fédérale sur le Tribunal fédéral du 17 juin 2005 (LTF; RS 173.110) est entrée en vigueur le 1er janvier 2007 (RO 2006 1205, 1242). L'acte attaqué ayant été rendu avant cette date, la procédure reste régie par l'OJ (<ref-law>; <ref-ruling> consid. 1.2 p. 395).
2. Le jugement entrepris porte sur des prestations de l'assurance-invalidité, de sorte que le Tribunal fédéral examine uniquement si l'autorité cantonale de recours a violé le droit fédéral, y compris l'excès et l'abus du pouvoir d'appréciation, si les faits pertinents ont été constatés de manière manifestement inexacte ou incomplète ou s'ils ont été établis au mépris de règles essentielles de procédure (art. 132 al. 2 OJ [dans sa teneur selon le ch. III de la loi fédérale du 16 décembre 2005 portant modification de la LAI, en vigueur depuis le 1er juillet 2006], en relation avec les art. 104 let. a et b, ainsi que 105 al. 2 OJ).
3. Est litigieux en l'espèce le droit de l'intimé à un quart de rente d'invalidité, plus particulièrement l'octroi de cette prestation au regard d'une décision initiale de refus entrée en force.
3.1 Le jugement entrepris expose correctement les dispositions légales sur la notion d'invalidité (art. 28 al. 1 et 2 LAI), et son évaluation chez les assurés actifs (<ref-law>). Il convient d'y renvoyer sur ces points. On ajoutera que lorsque l'administration est saisie d'une nouvelle demande sur laquelle elle est entrée en matière selon l'art. 87 al. 4 en lien avec l'al. 3 RAI, il convient d'examiner, par analogie avec l'<ref-law> (<ref-ruling> consid. 3.2 p. 75ss), si entre la décision de refus de prestations entrée en force et la décision litigieuse, un changement important des circonstances propre à influencer le degré d'invalidité, et donc le droit à la rente, s'est produit (<ref-ruling> consid. 3.5.2 p. 351).
3.2 En l'espèce, les premiers juges ont constaté, de manière à lier la Cour de céans (cf. consid. 2), que depuis l'entrée en force de la décision initiale de refus de prestations, l'état de santé de l'intimé n'a subi aucun changement. Il en découle que l'octroi d'un quart de rente n'est pas justifié, conformément à l'<ref-law> applicable par analogie.
La juridiction cantonale a considéré que la décision initiale de refus de prestations de l'OCAI (décision sur opposition du 22 avril 2004) était manifestement erronée dans la mesure où, pour le calcul du degré d'invalidité, un abattement de 10 % du revenu d'invalide avait été retenu. Selon les juges cantonaux, seule une réduction de 25 % permettait de tenir compte des limitations fonctionnelles de l'intimé, ce qui entraînait, après une nouvelle comparaison des revenus, un degré d'invalidité de 43,4 %, lequel ouvrait droit à un quart de rente. Ce faisant, la juridiction cantonale a, comme le soulève à juste titre l'office recourant, violé le principe jurisprudentiel, toujours valable sous l'empire de l'<ref-law>, selon lequel, si l'administration peut en tout temps revenir sur une décision formellement passée en force (aux conditions posées par la jurisprudence : voir <ref-ruling> consid. 2c p. 468s.), le juge des assurances sociales ne peut la contraindre à reconsidérer pareille décision (cf. ATF 119 V 4795 consid. 1b/cc p. 479, 117 V 8 consid. 2a p. 12s.). En outre, le juge n'est pas davantage habilité, en l'absence d'une disposition idoine, à lui imposer les modalités d'un tel réexamen (<ref-ruling> consid. 3b p. 184; SVR 1995 AHV n° 71 pp. 215-216 consid. 2a). En annulant la décision passée en force du 22 avril 2004, les premiers juges ont ainsi outrepassé leurs compétences. Il en découle que le jugement du 23 novembre 2006 est contraire au droit fédéral. Les arguments invoqués par l'intimé ne sauraient rien y changer.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et le jugement du Tribunal cantonal des assurances sociales du 23 novembre 2006 est annulé.
2. Les frais de justice, d'un montant de 500 fr., sont mis à la charge de l'intimé.
3. L'avance de frais effectuée par l'office recourant, d'un montant de 500 fr., lui est restituée.
4. Le présent arrêt sera communiqué aux parties, au Tribunal cantonal des assurances sociales de la République et canton de Genève et à l'Office fédéral des assurances sociales.
Lucerne, le 2 avril 2007
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière: