Actin polymerization is ubiquitously utilized to power the locomotion of eukaryotic cells and pathogenic bacteria in living systems. Inevitably, actin polymerization and depolymerization proceed in a fluctuating environment that renders the locomotion stochastic. Previously, we have introduced a deterministic model that manages to reproduce actin-propelled trajectories in experiments, but not to address fluctuations around them. To remedy this, here we supplement the deterministic model with noise terms. It enables us to compute the effects of fluctuating actin density and forces on the trajectories. Specifically, the mean-squared displacement (MSD) of the trajectories is computed and found to show a super-ballistic scaling with an exponent 3 in the early stage, followed by a crossover to a normal, diffusive scaling of exponent 1 in the late stage. For open-end trajectories such as straights and S-shaped curves, the time of crossover matches the decay time of orientational order of the velocities along trajectories, suggesting that it is the spreading of velocities that leads to the crossover. We show that the super-ballistic scaling of MSD arises from the initial, linearly increasing correlation of velocities, before time translational symmetry is established. When the spreading of velocities reaches a steady state in the long-time limit, short-range correlation then yields a diffusive scaling in MSD. In contrast, close-loop trajectories like circles exhibit localized periodic motion, which inhibits spreading. The initial super-ballistic scaling of MSD arises from velocity correlation that both linearly increases and oscillates in time. Finally, we find that the above statistical features of the trajectories transcend the nature of noises, be it additive or multiplicative, and generalize to other self-propelled systems that are not necessarily actin based.