Faits: A. Entre le 31 janvier et le 3 octobre 2008, A._ a fait l'objet de plus de vingt rapports de contravention pour mendicité et exercice d'une profession ambulante sans s'être acquittée de la taxe journalière idoine. Ces contraventions lui ont été notifiées par publications dans la Feuille d'avis officielle du canton de Genève. Le 3 octobre 2008, la police a saisi sur la prénommée les sommes de 8 fr. et 7 euros. Le 29 novembre 2011, A._ a demandé au Service des contraventions du canton de Genève (ci-après: le Service des contraventions) de lui restituer un montant de 2'588 fr., qui aurait été confisqué par des gendarmes aux fins d'acquitter des amendes qui ne lui auraient pas été notifiées. Le 7 février 2012, ce service lui a demandé de lui communiquer les références des amendes en question et de lui faire parvenir une copie des quittances de saisies. A._ a répondu que les amendes n'avaient jamais été notifiées et que les doubles des quittances demandées devaient figurer dans son dossier. Elle a donc réitéré sa requête, la dernière fois le 8 mars 2012. Le 14 mars 2012, le Service des contraventions l'a informée du fait que son dossier était transmis à son service juridique. Le 23 avril 2012, il a répondu à la prénommée qu'il n'envisageait pas la restitution des sommes prélevées, en se référant à une "décision matérielle" qualifiée de valable et en précisant qu'il allait procéder à "une nouvelle notification". B. Dans l'intervalle, par acte du 12 avril 2012, A._ avait formé un recours pour déni de justice auprès de la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice). Celle-ci a statué par arrêt du 15 mai 2012, en déclarant le recours irrecevable. Elle a d'abord relevé que le recours était devenu sans objet dès lors qu'il visait à obtenir une décision formelle qui a finalement été rendue le 23 avril 2012. Quant à la décision portant sur la saisie alléguée de 2'588 fr., elle ne figurait pas au dossier. A teneur du courrier du 23 avril 2012, il semblait toutefois que le Service des contraventions ait l'intention de procéder à une nouvelle notification de cette décision, que la recourante pourrait contester en temps voulu. La Cour de justice a encore fait des considérations sur le fond, en relevant que le séquestre semblait a priori conforme à l'art. 268 du code de procédure pénale suisse (CPP; RS 312.0). C. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler cet arrêt, de constater le déni de justice du Service des contraventions et d'ordonner audit service de rendre une décision formelle sur sa requête du 29 novembre 2011, subsidiairement de renvoyer la cause à l'autorité cantonale pour nouvelle décision. Invoquant les art. 29 Cst. et 6 CEDH, elle se plaint d'un déni de justice en raison d'un retard injustifié à statuer sur sa requête. Elle sollicite en outre l'octroi de l'assistance judiciaire. La Cour de justice et le Service des contraventions ont présenté des observations, concluant à l'irrecevabilité du recours, subsidiairement à son rejet. A._ a formulé des observations complémentaires. 