Faits:
A. Le 27 février 2006, J._ (née en 1967) a présenté une demande de prestations de l'assurance-invalidité (tendant à l'octroi d'une orientation professionnelle), qui a été rejetée par l'Office cantonal genevois de l'assurance-invalidité (ci-après: l'office AI) le 25 avril 2008. Deux mois après ce refus, le 25 juin 2008, l'assurée a déposé une nouvelle demande visant à l'allocation d'une rente d'invalidité, en invoquant souffrir d'un trouble dépressif présent depuis environ 2004. Par décision du 22 septembre 2008 (reprenant un projet de décision du 24 juillet précédent), l'office AI n'est pas entré en matière sur la demande, au motif que l'intéressée n'avait pas rendu vraisemblable une modification des faits.
B. Saisi d'un recours de l'assurée contre cette décision, le Tribunal cantonal des assurances sociales l'a rejeté par jugement du 2 décembre 2008.
C. J._ interjette un recours en matière de droit public contre le jugement cantonal, dont elle demande l'annulation. Sous suite de frais et dépens, elle conclut au renvoi de la cause à l'office AI pour qu'il rende une décision sur le droit à une rente d'invalidité. Elle 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. 1.1 Le litige porte sur le point de savoir si l'intimé était tenu d'entrer en matière sur la demande de rente du 25 juin 2008, respectivement si le jugement entrepris, par lequel le bien-fondé du refus d'entrer en matière a été admis, est conforme au droit.
1.2 Comme l'expose le jugement entrepris, en rappelant la teneur de l'art. 87 al. 3 et 4 RAI (en relation avec l'<ref-law>), lorsque la rente ou l'allocation pour impotent - ou encore, par analogie, les mesures de réadaptation (<ref-ruling>) - a été refusée parce que le degré d'invalidité était insuffisant ou parce qu'il n'y avait pas d'impotence, la nouvelle demande ne peut être examinée que si l'assuré rend plausible que son invalidité ou son impotence s'est modifiée de manière à influencer ses droits. Cette exigence doit permettre à l'administration qui a précédemment rendu une décision de refus de prestations entrée en force d'écarter sans plus ample examen de nouvelles demandes dans lesquelles l'assuré se borne à répéter les mêmes arguments, sans alléguer une modification des faits déterminants (<ref-ruling> consid. 5.2.3 p. 68, 117 V 198 consid. 4b p. 200 et les références). Lorsqu'elle est saisie d'une nouvelle demande, l'administration doit commencer par examiner si les allégations de l'assuré sont, d'une manière générale, plausibles. Si tel n'est pas le cas, l'affaire est liquidée d'entrée de cause et sans autres investigations par un refus d'entrée en matière (<ref-ruling> consid. 3a p. 198).
2. 2.1 Au regard du prononcé du 25 avril 2008 entré en force, qu'ils ont qualifié de décision de refus de toute prestation, les premiers juges ont considéré, à l'instar de l'administration, que la recourante n'avait pas rendu plausible que son état de santé s'était modifié de manière à influencer l'invalidité. Le nouvel avis médical qu'elle avait produit en procédure administrative n'avait pas mis en évidence une aggravation de son état de santé, mais constituait une appréciation différente de celui-ci. Aussi, était-ce à juste titre, toujours de l'avis des premiers juges, que l'intimé n'était pas entré en matière sur la nouvelle demande de la recourante.
2.2 Les considérations de la juridiction cantonale ne sauraient être suivies. Les normes réglementaires et les principes jurisprudentiels sur les modalités de l'examen d'une nouvelle demande après que des prestations ont été refusées par une décision entrée en force ne concernent, selon leur sens et but exposés ci-avant (consid. 1.2 supra), que des demandes de prestations portant sur un objet identique. En revanche, l'assuré ne peut se voir opposer l'entrée en force d'un refus de prestations antérieur lorsqu'il fait valoir le droit à des prestations différentes, et donc un cas d'assurance différent (arrêt I 269/97 du 24 février 1998, in SVR 1999 IV n° 21 p. 64; cf. aussi <ref-ruling> consid. 4b p. 200). Au contraire, l'administration - et en cas de recours le juge - est tenue d'examiner de manière étendue sous l'angle des faits et du droit une demande de prestations certes nouvelle, mais qui porte sur une prétention différente de celle qui a fait l'objet de la décision de refus antérieure.
Comme le fait valoir à juste titre la recourante, la première décision de l'intimé (du 25 avril 2008) portait uniquement sur le refus de mesures d'ordre professionnel, singulièrement d'un reclassement, en réponse à la demande initiale de la recourante, qui requérait une orientation professionnelle. Au regard tant de l'intitulé ("Refus de reclassement") que des bases légales citées (<ref-law> sur le droit au reclassement) et des motifs de la décision, il apparaît que l'intimé s'est prononcé seulement sur le droit à la mesure de réadaptation mentionnée et non pas sur le droit à une rente d'invalidité. A cet égard, on ne saurait déduire, comme le fait à tort la juridiction cantonale, de la seule constatation dans la décision en cause selon laquelle l'assurée aurait été apte à reprendre son activité habituelle de concierge dès le 12 octobre 2005 que l'administration aurait statué sur le droit à la rente. Une telle décision, destinée à une assurée qui n'était à l'époque pas assistée d'un conseil juridique, aurait à tout le moins exigé que soient mentionnés les fondements légaux du droit à une rente et soit expliquée la notion d'invalidité, dont dépend ce droit. Par ailleurs, ce n'est qu'au moment de s'adresser la seconde fois à l'assurance-invalidité, par requête du 25 juin 2008, que la recourante a sollicité une rente après s'être vue refuser un reclassement professionnel. Dès lors qu'il s'agissait d'une nouvelle demande portant sur une prétention différente de celle qui a fait l'objet de la décision du 25 avril 2008, l'office AI était tenu d'entrer en matière sur la requête. Le recours se révèle en conséquence bien fondé.
3. Compte tenu de l'issue du litige, les frais de procédure seront supportés par l'intimé (<ref-law>). La recourante, qui obtient gain de cause, a droit à une indemnité de dépens à la charge de l'intimé (<ref-law>), de sorte que la demande d'assistance judiciaire qu'elle a présentée pour l'instance fédérale est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis. Le jugement du Tribunal cantonal des assurances sociales de la République et canton de Genève du 2 décembre 2008 et la décision de l'Office cantonal genevois de l'assurance-invalidité du 22 septembre 2008 sont annulés. La cause est renvoyée à l'Office cantonal genevois de l'assurance-invalidité pour qu'il examine le droit de J._ à une rente d'invalidité, puis rende une décision à ce sujet.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de l'intimé.
3. L'intimé versera à la recourante la somme de 2800 fr. à titre de dépens pour la dernière instance.
4. La cause est renvoyée au Tribunal cantonal des assurances sociales de la République et canton de Genève pour nouvelle décision sur les frais et les dépens de la procédure antérieure.
5. Le présent arrêt est 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 22 octobre 2009
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Meyer Moser-Szeless