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. 