Fatti: A. In seguito al suo matrimonio celebrato il 4 maggio 2000 con una cittadina svizzera A.A._, cittadino russo, è stato posto al beneficio di un permesso di dimora, rinnovato per l'ultima volta fino al 3 maggio 2005. Il 30 maggio 2000 è entrata in Svizzera sua figlia di primo letto B.A._, alla quale è stata accordata un'autorizzazione di soggiorno di medesima scadenza di quella del padre. Preso atto che i coniugi A._ non convivevano più, la Sezione dei permessi e dell'immigrazione del Dipartimento delle istituzioni del Cantone Ticino ha revocato, il 21 ottobre 2004, il permesso di dimora di A.A._ e, di riflesso, quello della figlia B.A._. La decisione è stata confermata in ultima istanza dal Tribunale federale svizzero il 22 marzo 2005 (inc. 2A.163/2005). Agli interessati è stato quindi fissato un termine al 30 giugno 2005 per lasciare il Cantone. Il 18 agosto 2006 il Dipartimento federale di giustizia e polizia ha confermato, su ricorso, il rigetto della domanda di riesame presentata l'11 giugno 2005 da A.A._ e B.A._ all'Ufficio federale della migrazione. Le competenti autorità cantonali hanno quindi fissato agli interessati un termine al 15 dicembre 2006 per lasciare la Svizzera, in seguito più volte prorogato per permettere alla ragazza di concludere gli anni scolastici. Il 7 settembre 2007 la Sezione dei permessi e dell'immigrazione ha ordinato a A.A._ e B.A._ di lasciare il Cantone entro il 31 dicembre 2007 e li ha informati che una nuova proroga non sarebbe stata loro concessa. Il ricorso esperito contro l'ordine di partenza è stato dichiarato inammissibile dal Consiglio di Stato l'8 gennaio 2008. B. Il 26 febbraio 2008 A.A._, appellandosi alla legge federale del 16 dicembre 2005 sugli stranieri entrata in vigore il 1° gennaio 2008 (LStr; RS 142.20), si è rivolto alla Sezione dei permessi e dell'immigrazione chiedendole di revocare la decisione del 21 ottobre 2004 e di ripristinare il suo permesso di dimora e quello della figlia. L'istanza è stata respinta il 28 febbraio successivo dalla citata autorità, rigetto confermato su ricorso dapprima dal Consiglio di Stato, il 18 marzo 2008, e poi dal Tribunale cantonale amministrativo, con sentenza del 28 maggio 2008. Ritenuto che alla vertenza si applicava l'abrogata legge federale del 26 marzo 1931 concernente la dimora e il domicilio degli stranieri (LDDS), la Corte ticinese è giunta alla conclusione che l'entrata in vigore della LStr non costituiva un fatto nuovo e rilevante tale da giustificare un riesame della revoca del 21 ottobre 2004. Ha poi aggiunto che quand'anche la nuova normativa fosse applicabile, l'interessato non poteva comunque dedurne un diritto a risiedere nel nostro Paese. C. Il 4 luglio 2008 A.A._ ha presentato un ricorso in materia di diritto pubblico dinanzi al Tribunale federale, con cui chiede che la sentenza cantonale sia annullata, con conseguente revoca della decisione del 21 ottobre 2004 e ripristino del suo permesso di dimora e di quello della figlia. Sostiene di adempiere i requisiti posti dall'art. 50 LStr ed afferma che la mancata applicazione di tale disposto lederebbe il principio della parità di trattamento. Postula inoltre il beneficio dell'assistenza giudiziaria per tutte le istanze di giudizio. Chiamati ad esprimersi la Sezione dei permessi e dell'immigrazione, il Tribunale cantonale amministrativo e il Consiglio di Stato, quest'ultimo rimettendosi al giudizio del Tribunale federale, non hanno presentato osservazioni e si sono limitati a riconfermarsi nelle rispettive decisioni. Da parte sua l'Ufficio federale della migrazione, dichiarando di allinearsi alle considerazioni delle autorità cantonali, ha proposto la reiezione del gravame. D. Con decreto presidenziale del 9 luglio 2008 è stata accolta l'istanza di conferimento dell'effetto sospensivo contenuta nel ricorso.