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.

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).
2. Nell'impugnativa il ricorrente ha formulato delle conclusioni anche a favore della figlia, la quale era minorenne quando ha depositato l'allegato ricorsuale. Sennonché la ragazza non è designata come ricorrente e niente nella motivazione del gravame si riferisce alla sua situazione, limitandosi infatti il padre ad esprimersi sul proprio caso. Nella misura in cui egli era intenzionato a ricorrere a nome e per conto della figlia, l'impugnativa non soddisfa minimamente le esigenze di motivazione poste dall'art. 42 cpv. 2 LTF e, per quanto la concerne, è quindi inammissibile.
3. 3.1 Conformemente all'art. 83 lett. c n. 2 LTF, il ricorso in materia di diritto pubblico è inammissibile contro 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.
3.2 Come già spiegato da questa Corte, trattandosi non del rilascio iniziale o della proroga bensì della revoca di un permesso già concesso, detto rimedio è ricevibile nei casi in cui, senza la revoca, l'autorizzazione avrebbe ancora effetti giuridici (cfr. sentenze 2C_21/2007 del 16 aprile 2007 consid. 1.2 e 2D_8/2007 del 24 maggio 2007 consid. 1.2.1 e riferimenti). Sennonché nel caso concreto il permesso di cui fruiva il ricorrente è oramai scaduto dal 3 maggio 2005. Di conseguenza egli non ha più un interesse degno di protezione all'annullamento o alla modifica della decisione litigiosa (art. 89 cpv. 1 lett. c LTF): al riguardo il ricorso è pertanto irricevibile.
Rimane da valutare la fattispecie dal profilo del rinnovo, rispettivamente del rilascio di un nuovo permesso di dimora.
Rimane da valutare la fattispecie dal profilo del rinnovo, rispettivamente del rilascio di un nuovo permesso di dimora.
3.3 3.3.1 La legge federale del 26 marzo 1931 concernente la dimora e il domicilio degli stranieri (LDDS) è stata abrogata con l'entrata in vigore, il 1° gennaio 2008, della legge federale del 16 dicembre 2005 sugli stranieri (LStr; RS 142.20; cifra I dell'allegato all'art. 1245 LStr). Giusta l'art. 126 LStr, alle domande presentate prima dell'entrata in vigore della nuova legge permane applicabile il diritto previgente.
3.3.2 Se si condivide l'opinione del Tribunale amministrativo cantonale e si ritiene la presente vertenza assoggettata alla LDDS (cfr. sentenza impugnata pag. 4 consid. 1.1) ne discende che - come emerge dagli atti di causa - siccome è tuttora formalmente coniugato con una cittadina svizzera, il ricorrente ha di principio diritto alla proroga del permesso di dimora in base all'art. 7 cpv. 1, prima frase LDDS (RU 1991 1042). La fattispecie non ricade quindi sotto la clausola di esclusione dell'art. 83 lett. c n. 2 LTF ed il ricorso in materia di diritto pubblico risulta ammissibile.
Sennonché il ricorrente, il quale ammette che la revoca pronunciata nel 2004 era conforme al diritto, non ridiscute più la sentenza cantonale dal profilo della LDDS, in particolare non pretende di avere diritto al rilascio, rispettivamente alla proroga dell'autorizzazione di soggiorno in virtù dell'art. 7 LDDS. In ogni caso, questo aspetto è già stato definitivamente trattato nella precedente sentenza di questa Corte del 22 marzo 2005 (inc. 2A.163/2005) e non può più essere rimesso in discussione.
Sennonché il ricorrente, il quale ammette che la revoca pronunciata nel 2004 era conforme al diritto, non ridiscute più la sentenza cantonale dal profilo della LDDS, in particolare non pretende di avere diritto al rilascio, rispettivamente alla proroga dell'autorizzazione di soggiorno in virtù dell'art. 7 LDDS. In ogni caso, questo aspetto è già stato definitivamente trattato nella precedente sentenza di questa Corte del 22 marzo 2005 (inc. 2A.163/2005) e non può più essere rimesso in discussione.
3.4 3.4.1 Il ricorrente sostiene invece di avere un diritto all'autorizzazione richiesta in virtù dell'art. 50 cpv. 1 lett. a LStr. Tale norma sancisce che dopo lo scioglimento del matrimonio o della comunità familiare, il diritto del coniuge e dei figli al rilascio o alla proroga del permesso di dimora sussiste, tra l'altro, per i familiari di cittadini svizzeri, se l'unione coniugale è durata almeno tre anni e l'integrazione è avvenuta con successo. L'insorgente sostiene di adempiere i requisiti posti dal menzionato disposto nonché afferma che l'art. 126 LStr non si applica alle vertenze disciplinate dall'art. 50 LStr. In caso contrario si creerebbero, a suo avviso, insopportabili e inaccettabili disparità di trattamento a dipendenza che lo scioglimento del matrimonio è intervenuto poco prima o poco dopo l'entrata in vigore della nuova normativa. Infine contesta il richiamo, secondo lui del tutto improprio, della Corte cantonale al Messaggio dell'8 marzo 2002 concernente la nuova legge sugli stranieri siccome il progetto di legge che accompagnava (l'art. 49 che trattava dei motivi personali che rendevano necessario il prosieguo del soggiorno in Svizzera) è del tutto diverso da quello adottato (l'art. 50 che mira all'integrazione).
3.4.2 È incontestato che il ricorrente vive separato dalla moglie dal mese di luglio 2004 e che da allora non vi sono stati cambiamenti nella sua situazione matrimoniale. È altresì incontestato che la revoca del permesso di dimora di cui fruiva - il quale è comunque scaduto il 3 maggio 2005 - è stata confermata da questa Corte con sentenza del 22 marzo 2005. Al riguardo va precisato che da allora la sua presenza in Svizzera è unicamente tollerata (cfr. le proroghe successive del termine di partenza concessegli), motivo per cui questo periodo non può essere preso in considerazione per determinare la sua situazione famigliare e sociale. Da quel che precede discende che tutti gli elementi determinanti ai fini del giudizio sono accaduti nel passato ed erano conclusi da anni quando è entrata in vigore la nuova legge sugli stranieri. Orbene oltre al fatto che una nuova normativa non può ripristinare dei diritti - in concreto quello al rilascio, rispettivamente alla proroga di un'autorizzazione di soggiorno - scaduti, rispettivamente estinti da tempo, la sua applicazione alla presente fattispecie configurerebbe un caso di retroattività (propria) di principio vietata, salvo eccezioni non realizzate in concreto (RtiD 2007 I pag. 15 consid. 2.2 e rinvii).
È quindi chiaro che trattandosi di fattispecie che, come in concreto, si sono interamente svolte anni prima dell'entrata in vigore della LStr, le stesse rimangono sottoposte, rispettivamente vanno trattate in applicazione della previgente legislazione, cioè la LDDS. Ne discende che l'art. 50 LStr non si applica nel caso di specie: il ricorrente non può quindi vantare un diritto ad ottenere un permesso di dimora in applicazione di tale disposto. Da questo profilo la via del ricorso in materia di diritto pubblico non è aperta e il gravame è pertanto irricevibile.
È quindi chiaro che trattandosi di fattispecie che, come in concreto, si sono interamente svolte anni prima dell'entrata in vigore della LStr, le stesse rimangono sottoposte, rispettivamente vanno trattate in applicazione della previgente legislazione, cioè la LDDS. Ne discende che l'art. 50 LStr non si applica nel caso di specie: il ricorrente non può quindi vantare un diritto ad ottenere un permesso di dimora in applicazione di tale disposto. Da questo profilo la via del ricorso in materia di diritto pubblico non è aperta e il gravame è pertanto irricevibile.
3.5 Infine, nella misura in cui l'impugnativa non soddisfa minimamente le esigenze di motivazione previste dagli art. 116 e 117 in relazione con l'art. 106 cpv. 2 LTF per il ricorso sussidiario in materia costituzionale, non avendo il ricorrente evocato la violazione di alcun diritto costituzionale, anche trattato come tale (cfr. art. 113 LTF), il ricorso è irricevibile.
4. La domanda di assistenza giudiziaria contenuta nel gravame non può trovare accoglimento, atteso che le conclusioni del ricorrente erano sin dall'inizio prive di probabilità di successo (art. 64 LTF). Le spese seguono la soccombenza e vanno poste a suo carico (art. 65 e 66 cpv. 1 LTF). Non si concedono ripetibili ad autorità vincenti intervenute in causa nell'esercizio delle loro attribuzioni ufficiali (art. 68 cpv. 3 LTF).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. La domanda di assistenza giudiziaria è respinta.
3. Le spese giudiziarie di fr. 1'500.-- sono poste a carico del ricorrente.
4. Comunicazione al patrocinatore del 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.