We obtain a sample of 87 radio-loud quasi-stellar objects (QSOs) in the redshift range 3.6<=z<=4.4 by cross-correlating sources in the Faint Images of the Radio Sky at Twenty-Centimeters (FIRST) radio survey (S_1.4GHz_>1mJy) with star-like objects having r<20.2 in Sloan Digital Sky Survey (SDSS) Data Release 7. Of these 87 QSOs, 80 are spectroscopically classified in previous work (mainly SDSS), and form the training set for a search for additional such sources. We apply our selection to 2916 FIRST-DR7 pairs and find 15 likely candidates. Seven of these are confirmed as high-redshift quasars, bringing the total to 87. The candidates were selected using a neural-network, which yields 97 percent completeness (fraction of actual high-z QSOs selected as such) and an efficiency (fraction of candidates which are high-z QSOs) in the range of 47-60 percent. We use this sample to estimate the binned optical luminosity function (LF) of radio-loud QSOs at z~4, and also the LF of the total QSO population and its comoving density. Our results suggest that the radio-loud fraction at high z is similar to that at low z and that other authors may be underestimating the fraction at high z. Finally, we determine the slope of the optical LF and obtain results consistent with previous studies of radio-loud QSOs and of the whole population of QSOs. The evolution of the LF with redshift was for many years interpreted as a flattening of the bright-end slope, but has recently been re-interpreted as strong evolution of the break luminosity for high-z QSOs, and our results, for the radio-loud population, are consistent with this.