Fatti:
A. Entrato in Svizzera l'11 gennaio 1994 A.A._, cittadino serbo, vi si è sposato il 16 febbraio successivo con una connazionale titolare di un permesso di dimora. In seguito al matrimonio pure egli si è visto concedere un permesso di questo tipo, il quale è stato regolarmente rinnovato, l'ultima volta fino al 3 aprile 2008. Il 3 gennaio 1995 è nata la figlia B.A._, la quale ha ottenuto la cittadinanza svizzera il 27 febbraio 2007. Cessata la convivenza nel 1999, i coniugi A._ hanno divorziato il 19 giugno 2007. La figlia è stata affidata alla madre, mentre il padre ha ottenuto un diritto di visita ed è stato astretto a versarle un contributo alimentare.
Durante il suo soggiorno in Svizzera A.A._ ha interessato le autorità giudiziarie penali. Il 30 novembre 1998 il Procuratore pubblico gli ha inflitto una multa di fr. 300.-- per vie di fatto nei confronti della moglie e, il 18 giugno 2001, un'altra multa di fr. 400.-- per lesioni semplici, ridotta su opposizione a fr. 300.--. Un successivo ricorso è stato dichiarato irricevibile il 3 maggio 2002.
A.A._ è stato periodicamente a carico dell'assistenza pubblica, alla quale anche sua figlia ha dovuto ricorrere siccome il padre non le versava regolarmente gli alimenti. Vista la precaria situazione finanziaria dell'interessato la Sezione dei permessi e dell'immigrazione ha rifiutato, il 19 maggio 2004, di rilasciargli un permesso di domicilio nonché l'ha ammonito a due riprese (25 maggio 2005 e 9 maggio 2006) nel senso che se la situazione perdurava sarebbe stato espulso o rimpatriato.
B. Caduto nuovamente a carico dell'assistenza pubblica nell'agosto 2007, con un debito ammontante all'epoca a fr. 88'964.--, A.A._ si è visto rifiutare il 16 aprile 2008 il rinnovo del permesso di dimora nonché fissare un termine con scadenza al 30 giugno successivo per lasciare il Cantone.
La decisione è stata confermata su ricorso dapprima dal Consiglio di Stato, il 24 giugno 2008, e poi dal Tribunale cantonale amministrativo, con sentenza del 16 aprile 2009.
C. Il 19 maggio 2009 A.A._ ha presentato dinanzi al Tribunale federale un ricorso con cui chiede che il giudizio impugnato sia annullato e che gli sia rinnovato il permesso di dimora, in via subordinata che gli atti vengano rinviati all'autorità precedente per nuovo esame. Censura, in sintesi, la violazione dell'art. 8 CEDU e del principio della proporzionalità. Postula inoltre il beneficio dell'assistenza giudiziaria nel senso di essere esentato dal pagare spese giudiziarie.
Chiamati ad esprimersi, il Tribunale cantonale amministrativo si è riconfermato nelle motivazioni e conclusioni della propria sentenza, mentre il Consiglio di Stato si è rimesso al giudizio di questa Corte. La Sezione dei permessi e dell'immigrazione ribadisce e rinvia alle osservazioni formulate in sede cantonale, mentre l'Ufficio federale della migrazione dichiara di allinearsi alle considerazioni delle autorità ticinesi.
D. Con decreto presidenziale del 25 maggio 2009 è stata accolta l'istanza di conferimento dell'effetto sospensivo contenuta nel ricorso.
E. Il 14 settembre 2009 il ricorrente ha chiesto al Tribunale federale un'attestazione sui termini di trattazione del suo gravame da trasmettere agli istituti sociali della città di Lugano ai quali si era rivolto chiedendo un aiuto finanziario.

Diritto:
1. Il Tribunale federale esamina d'ufficio e con piena cognizione la sua competenza (art. 29 cpv. 1 LTF), rispettivamente l'ammissibilità dei gravami che gli vengono sottoposti (<ref-ruling> consid. 1; <ref-ruling> consid. 1.1 con riferimenti).
Il ricorrente ha omesso di precisare per quale via di diritto intendeva procedere. Tale imprecisione non comporta comunque alcun pregiudizio per lui, se il suo allegato adempie le esigenze formali del tipo di ricorso effettivamente esperibile (<ref-ruling> consid. 1.2; <ref-ruling> consid. 1.2 con rinvii).
L'impugnativa è stata presentata contro una decisione di ultima istanza cantonale in una causa di diritto pubblico; occorre quindi esaminare se la stessa sia ricevibile quale ricorso in materia di diritto pubblico.
2. 2.1 Giusta l'art. 83 lett. c n. 2 LTF, il ricorso in materia di diritto pubblico è inammissibile contro le decisioni in materia di diritto degli stranieri concernenti i permessi o autorizzazioni al cui ottenimento né il diritto federale né il diritto internazionale conferiscono un diritto (<ref-ruling> consid. 2.3; <ref-ruling> consid. 1). Il ricorrente non pretende - a ragione - trarre un simile diritto da norme legislative interne o da un trattato bilaterale concluso con Serbia e Montenegro, ma si prevale della garanzia al rispetto della vita privata e familiare sancita dall'art. 8 n. 1 CEDU.
2.2 Sua figlia è cittadina svizzera e ha, quindi, il diritto di risiedere stabilmente in Svizzera: a prima vista egli può pertanto prevalersi del diritto al ricongiungimento familiare garantito dall'art. 8 CEDU rammentato che, dal profilo dell'ammissibilità del gravame, non occorre verificare se tale diritto esista effettivamente (sentenze 2D_138/2008 del 10 giugno 2009 consid. 2.2 e 2D_98/2008 del 12 dicembre 2008, consid. 1.2). La via del ricorso in materia di diritto pubblico è quindi, in linea di massima, aperta.
2.3 Conformemente alla giurisprudenza, e come ricordato dal Tribunale amministrativo, il cittadino straniero che non ha la custodia dei figli può già di per sé vivere soltanto in misura limitata le relazioni con la prole, ossia unicamente nel quadro dell'esercizio del diritto di visita riconosciutogli. A questo scopo non è indispensabile che egli viva stabilmente nello stesso paese del figlio e che disponga pertanto di un'autorizzazione di soggiorno in detto Stato. Di principio il diritto di visita non implica quindi un diritto di presenza costante in Svizzera per il genitore straniero di un figlio che vi risiede in maniera regolare e durevole; le esigenze dell'art. 8 CEDU risultano rispettate già se il diritto di visita può venir esercitato nell'ambito di soggiorni di breve durata, adattandone se del caso le modalità (durata e frequenza). Un diritto all'ottenimento di un permesso di dimora può semmai sussistere solo se i rapporti con i figli sono particolarmente intensi dal profilo economico ed affettivo, se questi rapporti non potrebbero venir mantenuti a causa della distanza del paese d'origine del genitore e se il comportamento di quest'ultimo in Svizzera è stato irreprensibile. Solo a queste condizioni l'interesse pubblico ad una politica restrittiva in materia di soggiorno degli stranieri e d'immigrazione non risulta prevalente (sentenza 2C_657/2007 del 26 maggio 2008 consid. 2.4.3 e richiami).
Nel caso concreto, oltre al fatto che, come constatato nel giudizio impugnato ai cui pertinenti considerandi si rinvia (cfr. sentenza cantonale pag. 5 consid. 3.1 e pag. 7 consid. 3.4), il ricorrente è rimasto a lungo tempo a carico dell'assistenza pubblica e non ha avuto un comportamento irreprensibile, dagli atti di causa non emerge che intrattenga degli intensi rapporti con la figlia. Egli infatti non ha la custodia né detiene l'autorità parentale, ma dispone unicamente di un diritto di visita nei suoi confronti. Rilevato poi che non le versa, perlomeno non regolarmente, i contributi alimentari costringendola a rivolgersi pure lei all'assistenza pubblica, non si può quindi considerare che il loro legame abbia l'intensità e l'effettività richiesta dalla prassi.
2.4 Rimane da verificare la proporzionalità del provvedimento querelato. Anche se, come constatato dai giudici ticinesi, la partenza del ricorrente dalla Svizzera costituirà indubbiamente un ostacolo importante nel mantenimento delle relazioni familiari con la figlia, va ricordato che il genitore che non esercita la custodia, ma dispone unicamente di un diritto di visita, può già di per sé intrattenere una relazione familiare soltanto in maniera limitata: non è quindi indispensabile che viva nello stesso paese che la prole. E la relazione potrà essere mantenuta mediante contatti scritti e telefonici nonché nell'ambito di soggiorni turistici da organizzare, se del caso, con l'aiuto del curatore educativo che ha il compito di occuparsi delle relazioni padre-figlia e che saprà regolare al meglio il diritto di visita.
Per i motivi illustrati, il ricorrente non può dedurre nulla dal citato disposto convenzionale. Al riguardo il ricorso risulta infondato.
3. 3.1 In base alle considerazioni esposte, l'impugnativa si avvera manifestamente infondata e deve di conseguenza essere respinta in base alla procedura semplificata dell'art. 109 LTF.
3.2 L'istanza di assistenza giudiziaria non può trovare accoglimento in quanto il gravame appariva sin dall'inizio privo di probabilità di successo (art. 64 cpv. 1 LTF). Nell'addossare le spese giudiziarie al ricorrente soccombente (art. 66 cpv. 1 e 65 LTF) si considera la sua situazione finanziaria (art. 65 cpv. 2 LTF), fissando un importo ridotto. Non si assegnano ripetibili ad autorità vincenti (art. 68 cpv. 3 LTF).

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è respinto.
2. La domanda di assistenza giudiziaria è respinta.
3. Le spese giudiziarie di fr. 1'000.-- sono poste a carico del ricorrente.
4. Comunicazione al ricorrente, alla Sezione dei permessi e dell'immigrazione del Dipartimento delle istituzioni, al Consiglio di Stato e al Tribunale amministrativo del Cantone Ticino nonché all'Ufficio federale della migrazione.