Fatti: A. La presente vertenza trae origine dal licenziamento notificato il 26 aprile 2004 - con effetto al 1° novembre 2004 - dalla società Ferrovie federali svizzere FFS Cargo SA (di seguito FFS Cargo SA) ad A._, che dal 1° novembre 1979 lavorava alle dipendenze delle Officine delle FFS a Bellinzona, la cui gestione è stata appunto ripresa dalla citata società nel 2001. A.a. In particolare, la datrice di lavoro ha rimproverato al dipendente di aver disatteso gli obblighi comportamentali in caso di infortunio previsti dall'art. 94 del contratto collettivo di lavoro (CCL 2001-2003) e l'obbligo di diligenza e fedeltà di cui all'art. 321a cpv. 1 CO, partecipando a manifestazioni sportive agonistiche durante un periodo d'incapacità lavorativa. A._ ha immediatamente contestato i rimproveri mossigli da FFS Cargo SA, producendo documenti attestanti che la sua partecipazione alle varie gare era stata autorizzata dal medico curante e domandando di conseguenza la revoca del licenziamento. Essendo i suoi argomenti rimasti privi di riscontro positivo, il 27 ottobre 2004 egli ha interposto formale opposizione alla disdetta, a norma dell'art. 134 cpv. 2 CCL 2001-2003; dal canto suo, il 23 novembre seguente FFS Cargo SA ha confermato la propria posizione. A.b. Il 22 aprile 2005 A._ ha quindi convenuto FFS Cargo SA dinanzi alla Pretura del Distretto di Bellinzona chiedendo, in via principale, l'accertamento del suo diritto alla continuazione del rapporto di lavoro giusta l'art. 134 cpv. 3 CCL 2001-2003 e, in via subordinata, la condanna di controparte al pagamento di fr. 33'756.-- a titolo d'indennità per licenziamento ingiustificato oltre a fr. 8'000.-- per torto morale; in via ancora più subordinata ha domandato l'accertamento del diritto alle prestazioni in caso di malattia e infortunio e il versamento di un'indennità di fr. 33'756.--, pari a sei mesi di stipendio. FFS Cargo SA ha avversato le pretese attoree. Statuendo il 10 luglio 2007, il Pretore ha parzialmente accolto la petizione. Egli ha segnatamente accertato la sospensione del termine della disdetta del contratto di lavoro notificato da FFS Cargo SA ad A._, dal 19 ottobre 2004 fino al 31 luglio 2005, e ha condannato la società al versamento di fr. 22'500.--, oltre interessi al 5 % a far tempo dal giorno di emanazione della sentenza, a titolo d'indennità giusta l'art. 336a CO. A.c. Adita da entrambe le parti, con sentenza del 21 luglio 2008 la II Camera civile del Tribunale d'appello del Cantone Ticino, una volta stabilito che nella fattispecie difetta la giurisdizione civile, ha accertato la nullità della pronunzia pretorile e l'ha modificata dichiarando irricevibile la petizione. In breve, per i giudici ticinesi la vertenza in esame attiene al diritto pubblico e la competenza a giudicarla spetta al Tribunale federale amministrativo. B. Insorto dinanzi al Tribunale federale con un ricorso in materia civile datato 4 settembre 2008, A._ postula l'annullamento della sentenza cantonale e - accertata la competenza del Giudice civile a dirimere la lite - il rinvio degli atti alla II Camera civile del Tribunale d'appello del Cantone Ticino per un giudizio nel merito della causa. Nella risposta del 12 dicembre 2008 FFS Cargo SA ha aderito agli argomenti e alle domande ricorsuali. L'autorità cantonale ha invece rinunciato a presentare osservazioni.