Fractional Brownian motion, a Gaussian non-Markovian self-similar process with stationary long-correlated increments, has been identified to give rise to the anomalous diffusion behavior in a great variety of physical systems. The correlation and diffusion properties of this random motion are fully characterized by its index of self-similarity or the Hurst exponent. However, recent single-particle tracking experiments in biological cells revealed highly complicated anomalous diffusion phenomena that cannot be attributed to a class of self-similar random processes. Inspired by these observations, we here study the process that preserves the properties of the fractional Brownian motion at a single trajectory level; however, the Hurst index randomly changes from trajectory to trajectory. We provide a general mathematical framework for analytical, numerical, and statistical analysis of the fractional Brownian motion with the random Hurst exponent. The explicit formulas for probability density function, mean-squared displacement, and autocovariance function of the increments are presented for three generic distributions of the Hurst exponent, namely, two-point, uniform, and beta distributions. The important features of the process studied here are accelerating diffusion and persistence transition, which we demonstrate analytically and numerically.