We aim to obtain a complete sample of redshift > 3.6 radio QSOs from FIRST sources having star-like counterparts in the SDSS DR5 photometric survey (r<=20.2). We found that simple supervised neural networks, trained on sources with SDSS spectra, and using optical photometry and radio data, are very effective for identifying high-z QSOs without spectra. The technique yields a completeness of 96 per cent and an efficiency of 62 per cent. Applying the trained networks to 4415 sources without DR5 spectra we found 58 z>=3.6 QSO candidates. We obtained spectra of 27 of them, and 17 are confirmed as high-z QSOs. Spectra of 13 additional candidates from the literature and from SDSS DR6 revealed 7 more z>=3.6 QSOs, giving and overall efficiency of 60 per cent. None of the non-candidates with spectra from NED or DR6 is a z>=3.6 QSO, consistently with a high completeness. The initial sample of z>=3.6 QSOs is increased from 52 to 76, i.e. by a factor 1.46. From the new identifications and candidates we estimate an incompleteness of SDSS for the spectroscopic classification of FIRST 3.6<=z<=4.6 QSOs of 15 percent for r<=20.2.

16 pages, 9 figures accepted for publication in MNRAS