We develop a semi-analytical model to describe the cosmological evolution of networks of cosmic strings with small-scale structure, by extending the velocity-dependent one-scale model to include an additional lengthscale describing the typical interkink density. We study the impact of the different physical processes involved in the production and removal of small-scale structure from cosmic strings on the attainment of a full linear scaling regime, in which the characteristic lengths of the network and of small-scale structure evolve proportionally to physical time and the root-mean-squared velocity of the network remains constant. We find, using this novel velocity-dependent two-scale model, that quite generally small-scale structure does not prevent the attainment of a linear scaling regime since, even if not enough kinks are carried away when loops are chopped from the network, gravitational backreaction is generally enough to ensure that the interkink density scales. We find, however, that this regime is characterized by a smaller energy density and root-mean-squared velocity when compared to strings without small-scale structure and that this reduction may be significant when scaling is maintained by gravitational backreaction. In this case, we also find that, before reaching full scaling, the network should evolve in a transient quasi-scaling regime, in which its evolution is very similar to that of cosmic strings without small-scale structure.