Training a regression algorithm with a variable number of features
I think in the specific case that you have given as an example, you can use approach 1 which you have mentioned above i.e. 

either replace the missing features with a zero value 

or otherwise you can also 

implement your algorithm in a sparse manner so that it doesn't need to always have all the features for an instance. 

Using a sparse format will not affect the runtime (or any other aspect) of your algorithm. Whereas, if you use the zeroing features approach, then your algorithm will have to do the unnecessary multiply by zero operations and this will increase your runtime ( How much? that depends on how sparse is your actual data).

Hope that helps.