Fatti:
A. A._ è entrato alle dipendenze dello Stato del Cantone Ticino il 1° aprile 1981 quale giurista nominato a tempo pieno inizialmente presso l'Amministrazione cantonale delle contribuzioni e in seguito, a partire dal 1987, presso l'allora Dipartimento dell'educazione (ora: Dipartimento dell'educazione, della cultura e dello sport).
Il 24 agosto 2000 il Procuratore generale del Cantone Ticino ha aperto nei suoi confronti un procedimento penale per i titoli di denuncia mendace, tentata truffa, tentata estorsione, diffamazione, calunnia, minaccia, corruzione attiva e passiva, nonché violazione del segreto d'ufficio. Arrestato lo stesso giorno, l'accusato è stato posto in detenzione preventiva fino al 22 settembre 2000. Informato dell'arresto, il 24 agosto 2000 il Consiglio di Stato ha aperto a suo carico un procedimento disciplinare, sospendendolo immediatamente dalla funzione e privandolo dello stipendio nella misura del 50 %. L'inchiesta disciplinare, affidata al Cancelliere dello Stato e al Consulente giuridico del Governo, è stata contestualmente sospesa fino alla conclusione di quella penale.
B. Il 6 dicembre 2000 il Procuratore generale ha trasmesso all'Autorità amministrativa un rapporto e alcuni estratti dei verbali d'interrogatorio dell'accusato, oltre a un memoriale da questi prodotto in sede di interrogatorio. Preso atto degli accertamenti eseguiti dall'autorità penale, il 20 dicembre 2000 il Governo ha riattivato il procedimento disciplinare, nell'ambito del quale sono in particolare state svolte tre udienze ed è stata concessa all'interessato la facoltà di esprimersi. Dopo ulteriori atti, che non occorre qui evocare, con risoluzione del 4 settembre 2001 il Consiglio di Stato ha destituito A._ dalla carica di giurista. Gli ha sostanzialmente rimproverato di avere svolto per anni un'attività dipendente o indipendente non autorizzata e comunque manifestamente incompatibile con la funzione di impiegato dello Stato, accettando doni dall'avv. B._, con il quale aveva collaborato per anni e al quale aveva prestato consulenza, incorrendo, nell'ambito di queste attività, in specifiche violazioni del segreto d'ufficio, per avere fornito all'avv. B._ documenti interni di servizio a lui accessibili solo per la sua funzione. Il Governo gli ha inoltre rimproverato di avere fatto credere ad C._ e a persone a lui vicine di potere corrompere, grazie alla sua posizione, diversi funzionari per ottenere segnatamente permessi di dimora, creando a tal fine una certa messinscena, e di avere fatto ricorso a lettere anonime inviate ad un Consigliere di Stato, a due deputati del Gran Consiglio e all'Autorità federale, per prospettare reati di vario genere che sarebbero stati commessi dall'avv. B._, da C._, da funzionari e da altre persone, venendo in tal modo meno al dovere specifico di fedeltà e dignità nei confronti dell'amministrazione, che non è limitato alle esigenze peculiari del servizio ma si estende anche alla vita privata del dipendente.
C. Contro la decisione di destituzione, A._ ha adito il Tribunale cantonale amministrativo con un ricorso del 12 settembre 2001.
In pendenza di tale gravame, con sentenza del 12 febbraio 2008 del presidente della Pretura penale, si è concluso il procedimento penale: l'accusato è per finire stato riconosciuto colpevole di denuncia mendace e ripetuta violazione del segreto d'ufficio ed è stato condannato alla pena pecuniaria di 10 aliquote giornaliere di fr. 30.--, sospesa condizionalmente per un periodo di prova di due anni. Il reato di violazione del segreto d'ufficio concerne fatti commessi dopo la decisione governativa di destituirlo, riferendosi in particolare a segreti rivelati dall'accusato nella procedura ricorsuale dinanzi al Tribunale cantonale amministrativo.
Dopo un'udienza eseguita il 14 aprile 2008 dal presidente del Tribunale cantonale amministrativo in veste di giudice delegato, che ha proposto una transazione in seguito accettata da A._ ma non dal Consiglio di Stato, con sentenza dell'11 luglio 2008 la Corte cantonale ha confermato la decisione di destituzione.
D. A._ impugna questa decisione al Tribunale federale con un ricorso in materia di diritto pubblico e un ricorso sussidiario in materia costituzionale del 18 agosto 2008, chiedendo di annullarla e di rinviare gli atti alla Corte cantonale per un nuovo giudizio, che tenga conto della proposta di transazione formulata in sede di udienza. Il ricorrente fa valere la violazione del divieto dell'arbitrio nell'accertamento dei fatti e nella valutazione delle prove, come pure la violazione dei principi della buona fede, della parità di trattamento, della celerità e della proporzionalità. Postula inoltre di essere ammesso al beneficio dell'assistenza giudiziaria.
E. Invitata ad esprimersi sul gravame, la Corte cantonale si conferma nella sua sentenza, contestando di avere fornito al ricorrente un'assicurazione riguardo all'esito positivo della proposta di conciliazione. Il Consiglio di Stato postula invece la reiezione dei ricorsi nella misura della loro ammissibilità. Il ricorrente ha presentato, il 22 ottobre 2008, una replica alle osservazioni delle Autorità cantonali, le quali hanno ulteriormente ribadito le loro prese di posizione.

Diritto:
1. 1.1 Il Tribunale federale esamina d'ufficio e con piena cognizione la sua competenza (cfr. <ref-law>) e l'ammissibilità dei gravami che gli vengono sottoposti (<ref-ruling> consid. 1, 186 consid. 1).
1.2 Il ricorso in materia di diritto pubblico è segnatamente ammissibile contro le decisioni in materia di rapporti di lavoro di diritto pubblico concernenti controversie patrimoniali, se il valore litigioso raggiunge almeno fr. 15'000.-- (cfr. art. 82 lett. a in relazione con l'art. 83 lett. g e l'<ref-law>). La decisione impugnata concerne essenzialmente la sanzione disciplinare della destituzione pronunciata nei confronti del ricorrente. Benché questi non chieda esplicitamente il versamento di una somma di denaro, il gravame persegue almeno parzialmente uno scopo economico, siccome chiede che, invece della destituzione, sia pronunciata una disdetta amministrativa, la quale comporterebbe il pagamento dello stipendio trattenuto dopo la sospensione dalla carica, oltre a un'indennità di uscita. La controversia assume quindi natura patrimoniale e il valore litigioso minimo può essere considerato ampiamente raggiunto (cfr. <ref-law>; sentenza 1C_508/2008 del 22 dicembre 2008, consid. 1.2).
1.3 Il ricorrente ha partecipato al procedimento dinanzi all'autorità inferiore ed è particolarmente toccato dalla decisione di destituirlo dalla sua funzione. Egli ha un interesse degno di protezione all'annullamento o alla modifica del giudizio impugnato ed è quindi legittimato a ricorrere (<ref-law>). Il ricorso in materia di diritto pubblico, tempestivo (art. 100 cpv. 1 in relazione con l'<ref-law>) e diretto contro una decisione finale (<ref-law>), resa da un'autorità cantonale di ultima istanza (art. 86 cpv. 1 lett. d LTF), è quindi ammissibile. Il ricorso sussidiario in materia costituzionale ai sensi dell'art. 113 e segg. LTF è di conseguenza inammissibile.
1.4 Con il ricorso in materia di diritto pubblico si può fare valere la violazione del diritto, conformemente a quanto stabilito dagli art. 95 e 96 LTF. Secondo l'art. 42 cpv. 1 e 2 LTF, il ricorso dev'essere motivato in modo sufficiente. Il Tribunale federale esamina in linea di principio solo le censure sollevate; esso non è tenuto a vagliare, come lo farebbe un'autorità di prima istanza, tutte le questioni giuridiche che si pongono, se quest'ultime non sono presentate nella sede federale (<ref-ruling> consid. 1.4.1). Inoltre, quando, come in concreto, è invocata la violazione di diritti costituzionali, a norma dell'<ref-law> il Tribunale federale esamina le censure soltanto se siano motivate in modo chiaro e preciso, conformemente alla prassi precedentemente in vigore in materia di ricorso di diritto pubblico (cfr. <ref-ruling> consid. 2.2, 133 II 249 consid. 1.4.2). Il Tribunale federale statuisce di principio sulla base dei fatti accertati dall'autorità precedente (cfr. <ref-law>), riservati i casi previsti dall'<ref-law>. Questa disposizione gli conferisce la possibilità di rettificare o completare d'ufficio l'accertamento dei fatti della decisione impugnata nella misura in cui lacune o errori dovessero apparire d'acchito come manifesti. Il ricorrente può quindi contestare l'accertamento dei fatti determinanti per il giudizio solo se siano stati stabiliti in violazione del diritto ai sensi dell'<ref-law> o in maniera manifestamente inesatta (<ref-law>), vale a dire arbitraria, ciò che deve dimostrare con una motivazione conforme alle esigenze poste dall'<ref-law> (<ref-ruling> consid. 1.4.3).
Nella misura in cui il ricorrente, invocando la violazione di diritti costituzionali, presenta contro il giudizio impugnato argomentazioni generiche e di carattere essenzialmente appellatorio, diffondendosi in contestazioni che si riferiscono al procedimento penale, il gravame non adempie le citate esigenze di motivazione ed è pertanto inammissibile. Spettava infatti al ricorrente confrontarsi puntualmente con le considerazioni esposte nella sentenza della Corte cantonale, unico oggetto del litigio, spiegando per quali ragioni esse sarebbero lesive del diritto e contrarie alla giurisprudenza. In particolare, laddove è invocata la violazione del divieto dell'arbitrio, occorreva dimostrare per quali ragioni i fatti accertati sarebbero manifestamente in contrasto con gli atti e la decisione impugnata sarebbe del tutto insostenibile, in contraddizione manifesta con una norma o con un principio giuridico indiscusso o chiaramente lesiva del sentimento di giustizia e dell'equità (<ref-ruling> consid. 2.1, 129 I 8 consid. 2.1, 128 I 273 consid. 2.1 e rinvii).
2. 2.1 Il ricorrente espone inizialmente una serie di contestazioni in tema di divieto dell'arbitrio nell'accertamento dei fatti. Critica in particolare la descrizione degli stessi contenuta nel giudizio impugnato, rimproverando alla Corte cantonale di essersi fondata essenzialmente sui verbali di interrogatorio trasmessi dal Procuratore generale all'autorità amministrativa. Il ricorrente sostiene di avere contestato tali verbali, che conterrebbero ammissioni rese solo per ottenere la scarcerazione e comunque contraddittorie. Adduce inoltre che la Corte cantonale si sarebbe fondata a torto sia sull'accusa di denuncia mendace, non evocata dal Governo, sia su quella di violazione del segreto d'ufficio, riferita a circostanze successive alla destituzione. Né egli sarebbe stato condannato per avere accettato doni, richiamando altresì che la maggior parte dei capi d'imputazione sarebbe per finire caduta nel corso del procedimento penale. Il ricorrente rimprovera pure alla precedente istanza di non avere riportato nel giudizio l'udienza svoltasi il 14 aprile 2008 e la relativa proposta di transazione.
2.2 Come visto, il Procuratore generale ha trasmesso all'autorità amministrativa gli estratti dei verbali d'interrogatorio dell'accusato del 1° settembre, dell'11 settembre e del 22 settembre 2000, nonché un memoriale non datato redatto dall'accusato medesimo. Su questi documenti il ricorrente ha potuto ampiamente esprimersi nell'ambito della procedura disciplinare sia oralmente in sede di udienza sia per iscritto, presentando osservazioni e precisazioni al riguardo. Né il Consiglio di Stato né la Corte cantonale hanno quindi violato il diritto di essere sentito del ricorrente o sono incorse nell'arbitrio per essersi fondati sulle ammissioni rese dal ricorrente nel procedimento penale. D'altra parte, nelle sue prese di posizione, egli non ha seriamente messo in dubbio le inequivocabili dichiarazioni rilasciate al magistrato inquirente, ma ha piuttosto cercato di minimizzarle, spiegando le ragioni alla base del suo comportamento, la sua situazione finanziaria precaria e le circostanze della sua carcerazione preventiva. L'esercizio sull'arco di quasi un decennio di un'occupazione accessoria senza la necessaria autorizzazione e in particolare le modalità riprovevoli con cui è stata prestata la consulenza giuridica da parte del ricorrente, che ha quantomeno accettato l'inganno perpetrato dall'avv. B._, inducendo i clienti, e segnatamente C._, a versare somme superiori all'onorario, facendo loro credere che occorresse corrompere i funzionari competenti per il rilascio dei permessi, sono quindi stati accertati dalla precedente istanza in modo conforme agli atti e non sono seriamente smentiti dal ricorrente nemmeno in questa sede. Del tutto corrispondenti alle risultanze degli atti, e peraltro oggetto della definitiva condanna, sono pure le constatazioni riferite alle circostanze nelle quali il ricorrente ha screditato i suoi colleghi che sapeva innocenti, denunciandoli mendacemente mediante lettere anonime. Il fatto che nella decisione di destituzione il Governo non gli abbia esplicitamente addebitato il reato di denuncia mendace ai sensi dell'<ref-law> non è decisivo, ritenuto che tale autorità non era tenuta a esprimere un giudizio in merito alla rilevanza penale degli atti rimproveratigli, ma a valutarli sotto il profilo del diritto disciplinare (cfr. sentenza 2P.270/2000 del 26 gennaio 2001, consid. 3c/bb e 4b/cc). D'altra parte, la Corte cantonale non ha dato un peso determinante né ai doni che il ricorrente ha accettato dall'avv. B._ né alle imprecisate informazioni e ai documenti interni di servizio che avrebbe fornito a quest'ultimo, riconoscendo altresì esplicitamente che il reato di violazione del segreto d'ufficio, per il quale è stato condannato, era stato commesso dal ricorrente dopo l'emanazione della decisione di destituzione. È comunque in modo sostenibile che la Corte cantonale non ha approfondito questi aspetti, ritenendo, a ragione, che la destituzione del ricorrente si giustificava già sulla base delle gravi violazioni dei doveri di servizio legate sia alle modalità con cui aveva svolto le consulenze giuridiche sia al fatto di avere denunciato mediante lettere anonime persone e colleghi che sapeva innocenti.
La Corte cantonale nemmeno ha tralasciato di evocare nel suo giudizio l'udienza del 14 aprile 2008. Contrariamente all'opinione del ricorrente, che non sostanzia invero alcun arbitrio al riguardo, la precedente istanza non era tenuta a dilungarsi nei considerandi della sua decisione sui dettagli dell'udienza, dal momento che la transazione proposta dal giudice delegato era superata, non essendo stata accettata dal Consiglio di Stato.
3. 3.1 Il ricorrente sostiene che i giudici cantonali avrebbero dovuto contestualmente statuire anche sulle sue pretese di natura pecuniaria derivanti dal rapporto d'impiego, come sarebbe già avvenuto in altri casi, tanto più che in concreto il giudice delegato aveva formulato una proposta di transazione quantificabile in denaro.
3.2 Secondo l'art. 67 cpv. 1 lett. e della legge cantonale sull'ordinamento degli impiegati dello Stato e dei docenti, del 15 marzo 1995 (LOrd) in relazione con l'art. 68 della legge ticinese di procedura per le cause amministrative, del 19 aprile 1966 (LPamm), contro la decisione di destituzione è dato il ricorso al Tribunale cantonale amministrativo. Ove giudichi il licenziamento ingiustificato, esso lo accerta nella propria sentenza e nel medesimo giudizio o con giudizio separato secondo la procedura come istanza unica, ne stabilisce l'indennità (art. 69 cpv. 1 e 2 LPamm).
Giusta l'art. 68 LOrd in relazione con l'art. 71 segg. LPamm, le contestazioni per pretese di natura pecuniaria derivanti dal rapporto d'impiego devono essere presentate mediante petizione al Tribunale cantonale amministrativo quale istanza unica.
3.3 Premesso che il ricorrente non fa valere l'applicazione arbitraria delle suddette disposizioni, è senza violare le stesse o disattendere il divieto dell'arbitrio che la Corte cantonale ha fondato la sua competenza sugli art. 67 cpv. 1 lett. e LOrd e 68 LPamm ed ha quindi statuito unicamente sulla sanzione disciplinare, riservando se del caso al ricorrente la possibilità di avanzare eventuali pretese pecuniarie mediante una petizione dinanzi alla stessa Corte cantonale. L'indennità complessiva chiesta dal ricorrente è del resto sostanzialmente da lui riferita a una disdetta amministrativa e presuppone quindi che il provvedimento della destituzione sia ingiustificato. Poiché il licenziamento litigioso è invece stato ritenuto giustificato dalla Corte cantonale, è senz'altro ragionevole ch'essa abbia rinviato il ricorrente ad avanzare, se del caso, ulteriori pretese pecuniarie nell'ambito di una specifica procedura giusta gli art. 71 segg. LPamm. Il ricorrente non sostiene peraltro che questo modo di procedere gli causerebbe un pregiudizio. Inoltre, asserendo semplicemente che in passato la Corte cantonale avrebbe quantificato le pretese di funzionari licenziati, non rende verosimile una disparità di trattamento.
4. Sempre sotto il capitolo dell'arbitrio, il ricorrente si diffonde nel criticare i considerandi 3 e 4 della sentenza impugnata, riguardanti i motivi che giustificano la sanzione della destituzione. Lo fa tuttavia in modo generico, ribadendo in sostanza che la maggior parte delle accuse a suo carico sono state abbandonate in sede penale e sottolineando come il suo comportamento avrebbe permesso di accertare gravi reati commessi dall'avv. B._ e di rilevare disfunzioni all'interno dell'amministrazione pubblica, che portarono all'avvio di procedimenti penali e disciplinari contro altri funzionari e magistrati. Il ricorrente non sostanzia tuttavia alcun arbitrio negli accertamenti contenuti nella sentenza impugnata, né fa valere l'applicazione arbitraria delle disposizioni della LOrd che disciplinano i doveri di servizio del dipendente e le conseguenze della loro violazione. Né egli si confronta, singolarmente e in modo conforme alle citate esigenze di motivazione, con le ragioni che hanno condotto la precedente istanza a confermare la destituzione, spiegando puntualmente perché, tenuto conto della natura delle trasgressioni ai doveri di servizio, la sua rimozione non sarebbe una misura proporzionata agli interessi di tutela del buon funzionamento e dell'immagine dell'amministrazione pubblica. Come visto, la semplice circostanza che i comportamenti rimproverati al ricorrente non abbiano in parte assunto una rilevanza di carattere penale non significa ch'essi siano trascurabili sotto il profilo del diritto disciplinare. Al riguardo, spettava piuttosto al ricorrente spiegare per quali motivi la Corte cantonale avrebbe a torto ravvisato in tali comportamenti una violazione grave dei doveri di servizio.
5. 5.1 Il ricorrente lamenta una violazione del principio della buona fede per il fatto che, contrariamente a quanto avrebbe lasciato intendere il giudice delegato, il contenuto della transazione da questi proposta all'udienza del 14 aprile 2008 non è stato confermato nel giudizio impugnato. L'aspettativa di una conferma della proposta lo avrebbe d'altro canto indotto a rinunciare a chiedere l'assunzione di ulteriori prove utili alla difesa dei suoi interessi.
5.2 L'<ref-law> istituisce un diritto fondamentale del cittadino ad essere trattato secondo il principio della buona fede da parte degli organi dello Stato. In materia di diritto amministrativo, tale principio tutela l'amministrato nei confronti dell'autorità, quando, assolte determinate condizioni, il medesimo abbia agito conformemente alle istruzioni e alle dichiarazioni di quest'ultima. Il principio tutela in particolare la fiducia riposta in un'informazione ricevuta dall'autorità o in un suo determinato comportamento suscettibile di destare un'aspettativa legittima, quando l'autorità sia intervenuta in una situazione concreta riguardo a determinate persone, quand'essa era competente a rilasciare l'informazione o il cittadino poteva ritenerla competente sulla base di fondati motivi, quando affidandosi all'esattezza dell'informazione egli abbia preso delle disposizioni non reversibili senza subire un pregiudizio e quando non siano intervenuti mutamenti legislativi posteriori al rilascio dell'informazione stessa (<ref-ruling> consid. 8.1 pag. 60, 129 II 361 consid. 7.1, 129 I 161 consid. 4.1 e rinvii).
5.3 Il ricorrente non censura la violazione delle disposizioni procedurali in materia di conciliazione e transazione (art. 17 e 27 LPamm), ma si appella essenzialmente all'aspettativa che il comportamento del giudice delegato avrebbe suscitato in lui. Disattende tuttavia che nella fase dell'esperimento di conciliazione il giudice svolge prevalentemente un ruolo di mediatore. Affinché possa confrontarsi con le richieste e le concezioni delle parti, ricercando soluzioni consensuali nel loro interesse, agli atti di mediazione del giudice non devono essere poste esigenze troppo severe. Una proposta di transazione non deve quindi adempiere gli stessi requisiti di una sentenza, costituendo essenzialmente una base di discussione che non esclude di per sé anche altre soluzioni (cfr. sentenza 1P.32/1997 del 20 marzo 1997, consid. 5a). In concreto, dal verbale dell'udienza risulta che il giudice delegato ha proposto alle parti di comporre la vertenza mediante una transazione che prevedeva di sostituire la destituzione con una disdetta amministrativa e ne ha stabilito i dettagli. Ha quindi assegnato alle parti un termine per pronunciarsi sulla proposta, dando esplicitamente atto che in caso di rifiuto il Tribunale avrebbe statuito sul ricorso senza ulteriori formalità. Alla luce di queste circostanze, il ricorrente non poteva in buona fede ritenere che il giudice delegato gli avesse assicurato alcunché riguardo all'esito della proposta o al contenuto del giudizio che la Corte cantonale sarebbe stata chiamata a pronunciare. Un'assicurazione concreta in tal senso avrebbe peraltro esposto il giudice al rischio di una possibile domanda di ricusa della controparte (cfr. <ref-ruling> consid. 3.6 pag. 119 seg.; sentenza 1P.32/1997, citata, consid. 5a e 6). Il ricorrente medesimo riconosce del resto che durante l'udienza il rappresentante dello Stato aveva anticipato come difficilmente il Governo avrebbe accettato la proposta. Inoltre, nella sua precedente funzione di giurista presso l'allora Dipartimento dell'educazione egli, per sua stessa ammissione, si era già confrontato con controversie in materia di cessazione del rapporto d'impiego, sicché la procedura dinanzi alla Corte cantonale e in particolare la portata del verbale di udienza gli erano note. Queste circostanze nemmeno potevano, in buona fede, indurre il ricorrente a ritenere di potere rinunciare all'assunzione di ulteriori prove che considerava rilevanti confidando nel fatto che la Corte cantonale confermasse il contenuto della transazione. Al riguardo, egli non spiega, con una motivazione conforme alle già citate esigenze, quali specifiche prove, oltre alle sentenze penali da lui prodotte all'udienza, sarebbero ancora state decisive per la causa, rispettivamente per quali motivi, a meno di incorrere nell'arbitrio, la Corte cantonale non avrebbe comunque potuto rinunciare ad assumerle sulla base di un apprezzamento anticipato della loro rilevanza (cfr., sull'apprezzamento anticipato delle prove, <ref-ruling> consid. 2.1, 125 I 127 consid. 6c/cc, 417 consid. 7b).
6. 6.1 Il ricorrente lamenta una disparità di trattamento nell'illegalità, adducendo l'esistenza di almeno cinque casi di funzionari che, pur violando gravemente i loro doveri di servizio, non sono stati destituiti ma pensionati anticipatamente, oppure congedati mediante una disdetta amministrativa.
6.2 Può qui rimanere indecisa la questione di sapere se il ricorrente possa validamente prevalersi degli accennati casi analoghi, ritenuto ch'essi sono stati rivelati alla Corte cantonale violando il segreto d'ufficio e costituiscono quindi prove illecite (cfr. <ref-ruling> consid. 3). Egli si limita in effetti, essenzialmente, a rilevare che anche i funzionari citati sarebbero stati condannati penalmente, oltretutto a pene più severe e per reati più gravi. Non dimostra tuttavia che i casi evocati riguarderebbero comportamenti analoghi ai propri o violazioni dei doveri di servizio paragonabili. D'altra parte, richiamando cinque casi in cui il rapporto d'impiego sarebbe stato sciolto per altri motivi, il ricorrente non attesta l'esistenza in materia di sanzioni disciplinari di una prassi costante contraria alla legge, volta a rendere sistematicamente inapplicabile il provvedimento della destituzione. La circostanza secondo cui la legge non sia stata applicata o non sia stata applicata correttamente in pochi singoli casi non conferisce infatti, di massima, all'interessato che si trova nella medesima situazione un diritto di essere anch'egli trattato diversamente da quanto previsto dalla legge. Del resto, per potere invocare con successo il principio in questione è pure necessario che l'autorità chiamata a decidere lasci riconoscere che anche in futuro non si scosterà dalla prassi illegale, ciò che il ricorrente non allega (cfr. <ref-ruling> consid. 3a, 126 V 390 consid. 6a, 123 II 248 consid. 3c). In concreto, i presupposti per ammettere che il ricorrente possa eventualmente prevalersi, a titolo eccezionale, di un diritto alla parità di trattamento nell'illegalità non sono pertanto realizzati.
7. 7.1 Il ricorrente lamenta la violazione del principio di celerità con riferimento sia alla durata di quasi otto anni del procedimento penale sia a quella di quasi sette anni della procedura di ricorso al Tribunale cantonale amministrativo contro la decisione di destituzione del 4 settembre 2001.
7.2 Giusta l'<ref-law>, in procedimenti dinanzi ad autorità giudiziarie o amministrative, ognuno ha diritto alla parità ed equità di trattamento, nonché ad essere giudicato entro un termine ragionevole. Il carattere ragionevole della durata di una procedura deve essere valutato considerando globalmente le circostanze della stessa, tenendo in particolare conto dell'ampiezza e delle difficoltà del caso, nonché del comportamento delle parti e dell'autorità (cfr. <ref-ruling> consid. 3.3.3, 124 I 139 consid. 2c pag. 142).
7.3 Come riconosce il ricorrente stesso, della violazione del principio di celerità è stato rettamente tenuto conto nell'ambito del procedimento penale, segnatamente nella commisurazione della pena, e la questione non è oggetto del presente giudizio. Quanto alla durata della procedura amministrativa, egli ammette di avere sollecitato, comunque non per iscritto, il proseguimento della causa solo dopo l'emanazione, il 12 febbraio 2008, della sentenza di condanna definitiva. Egli ha quindi perlomeno implicitamente condiviso la sospensione della procedura di ricorso, invero non stabilita mediante una decisione formale, fino alla conclusione del procedimento penale. Dopo la pronuncia della sentenza 12 febbraio 2008 del presidente della Pretura penale, la procedura dinanzi alla Corte cantonale è tuttavia proseguita senza dilazioni, con lo svolgimento dell'udienza il 14 aprile 2008 e l'emanazione del giudizio l'11 luglio 2008. In tali circostanze, alla luce del consenso del ricorrente ad attendere l'esito del procedimento penale, non può essere rimproverato alla precedente istanza un ritardo nello statuire sul ricorso contro la decisione di destituzione.
8. 8.1 Ne segue che il ricorso in materia di diritto pubblico deve essere respinto in quanto ammissibile, mentre il ricorso sussidiario in materia costituzionale deve essere dichiarato inammissibile.
8.2 La domanda di assistenza giudiziaria presentata dal ricorrente deve essere respinta, essendo il gravame fin dall'inizio privo di possibilità di esito favorevole (<ref-law>). Le spese giudiziarie sono pertanto poste a suo carico, in considerazione della sua soccombenza (<ref-law>). Vista la sua situazione finanziaria, si giustifica tuttavia di prelevare una tassa di giustizia ridotta (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso in materia di diritto pubblico è respinto.
2. Il ricorso sussidiario in materia costituzionale è inammissibile.
3. La domanda di assistenza giudiziaria è respinta.
4. Le spese giudiziarie di fr. 500.-- sono poste a carico del ricorrente.
5. Comunicazione al ricorrente, al Consiglio di Stato e al Tribunale amministrativo del Cantone Ticino.