Must the assumed mean a always be one of the class marks of the table?

The identity $\bar{x}=a+\frac{\sum f_i{d}_i}{\sum f_i}$ holds for every a, since $\sum f_i(x_i-a)=\sum f_i{x}_i-a\sum f_i$ whatever a is. Choosing a to be a class mark is only a convenience: it makes each $d_i$ a whole multiple of $h$, so the $u_i=d_i/h$ of the step-deviation method are small integers. Choose some other a and the answer is still correct, just messier.