Gaia DR3 has offered the scientific community a remarkable dataset of approximately one million spectra acquired with the Radial Velocity Spectrometer (RVS) in the Calcium II triplet region, that is well-suited to identify very metal-poor (VMP) stars. However, over 40% of these spectra have no released parameters by Gaia's GSP-Spec pipeline in the domain of VMP stars, whereas VMP stars are key tracers of early Galactic evolution. We aim to provide spectroscopic metallicities for VMP stars using Gaia RVS spectra, thereby producing a catalogue of bright VMP stars distributed over the full sky that can serve as the basis to study early chemical evolution throughout the Galaxy. We select VMP stars using photometric metallicities from the literature and analyse the Gaia RVS spectra to infer spectroscopic metallicities for these stars. The inferred metallicities agree very well with literature high-resolution metallicities with a median systematic offset of 0.1dex and standard deviation of ~0.15dex. The purity of this sample in the VMP regime is ~80% with outliers representing a mere ~3%. We make available an all-sky catalogue of ~1500 stars with reliable spectroscopic metallicities down to [Fe/H]~-4.0, of which ~1000 are VMP stars. More than 75% of these stars have either no spectroscopic metallicity value in the literature to date or are flagged to be unreliable in their literature spectroscopic metallicity estimates. This catalogue of bright (G<13) VMP stars is three times larger than the current sample of well-studied VMP stars in the literature in this magnitude range, making it ideal for high-resolution spectroscopic follow-up and to study the properties of VMP stars in different parts of our Galaxy.