A stochastic model for variable-length stepping of kinesins engineered with extended neck linkers is developed. This requires consideration of the separation in microtubule binding sites between the heads of the motor at the beginning of a step. It can be shown that the separation is a stationary Markov process and can be included in the calculation of standard experimental quantities, such as asymptotic velocity and effective diffusion, through the appropriate limits of a semi-Markov process. Using this framework, asymptotic results for randomly detached motors are also obtained and linked to the statistical analysis of velocity data from motor assays. In addition, we will discuss how the framework developed here could be used as one component of a larger scale model for motor-cargo systems of the type to be presented in Kramer's talk.