We aim to obtain a complete sample of redshift z>=3.6 radio quasi-stellar objects (QSOs) from the Faint Images of the Radio Sky at Twenty cm survey (FIRST) sources (S_1.4GHz_>1mJy) having star-like counterparts in the Sloan Digital Sky Survey (SDSS) Data Release 5 (DR5) photometric survey (r_AB_<=20.2). Our starting sample of 8665 FIRST-DR5 pairs includes 4250 objects with spectra in DR5, 52 of these being z>=3.6 QSOs. We found that simple supervised neural networks, trained on the sources with DR5 spectra, and using optical photometry and radio data, are very effective for identifying high-z QSOs in a sample without spectra. For the sources with DR5 spectra the technique yields a completeness (fraction of actual high-z QSOs classified as such by the neural network) of 96 per cent, and an efficiency (fraction of objects selected by the neural network as high-z QSOs that actually are high-z QSOs) of 62 per cent. Applying the trained networks to the 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 Data Release 6 (DR6) revealed seven more z>=3.6 QSOs, giving an overall efficiency of 60 per cent (24/40).