Context. Among the myriad of data collected by the ESA Gaia satellite, about 150 million spectra will be delivered by the Radial Velocity Spectrometer (RVS) for stars as faint as GRVS~ 16. A specific stellar parametrization will be performed on most of these RVS spectra, i.e. those with enough high signal-to-noise ratio (S/N), which should correspond to single stars that have a magnitude in the RVS band brighter than ~14.5. Some individual chemical abundances will also be estimated for the brightest targets. Aims: We describe the different parametrization codes that have been specifically developed or adapted for RVS spectra within the GSP-Spec working group of the analysis consortium. The tested codes are based on optimisation (FERRE and GAUGUIN), projection (MATISSE), or pattern-recognition methods (Artificial Neural Networks). We present and discuss each of their expected performances in the recovered stellar atmospheric parameters (effective temperature, surface gravity, overall metallicity) for B- to K-type stars. The performances for determining of [α/Fe] ratios are also presented for cool stars. Methods: Each code has been homogeneously tested with a large grid of RVS simulated synthetic spectra of BAFGK-spectral types (dwarfs and giants), with metallicities varying from 10-2.5 to 10+ 0.5 the solar metallicity, and taking variations of ±0.4 dex in the composition of the α-elements into consideration. The tests were performed for S/N ranging from ten to 350. Results: For all the stellar types we considered, stars brighter than GRVS~ 12.5 are very efficiently parametrized by the GSP-Spec pipeline, including reliable estimations of [α/Fe]. Typical internal errors for FGK metal-rich and metal-intermediate stars are around 40 K in Teff, 0.10 dex in log(g), 0.04 dex in [M/H], and 0.03 dex in [α/Fe] at GRVS = 10.3. They degrade to 155 K in Teff, 0.15 dex in log(g), 0.10 dex in [M/H], and 0.1 dex in [α/Fe] at GRVS~ 12. Similar accuracies in Teff and [M/H] are found for A-type stars, while the log(g) derivation is more accurate (errors of 0.07 and 0.12 dex at GRVS = 12.6 and 13.4, respectively). For the faintest stars, with GRVS≳ 13-14, a Teff input from the spectrophotometric-derived parameters will allow the final GSP-Spec parametrization to be improved. Conclusions: The reported results, while neglecting possible mismatches between synthetic and real spectra, show that the contribution of the RVS-based stellar parameters will be unique in the brighter part of the Gaia survey, which allows for crucial age estimations and accurate chemical abundances. This will constitute a unique and precious sample, providing many pieces of the Milky Way history puzzle with unprecedented precision and statistical relevance.