Is debt servicing in the structural or cyclical budget balance? Are the interest payments on government debt to be considered in the structural or the cyclical budget balance?

I think, since it's independent on the state of the economy, then they should go to the structural budget balance, but I'm not sure.
The IMF methodology to determine the structural balance is given here: link to article.

I would summarise the methodology as: the sensitivity of budget components to the deviation of actual output from potential is estimated, as well as that deviation (the output gap). Taken together, that gives an estimate of the effect of the cycle on the budget balance.

It is unclear what estimates for their sensitivity of interest payments is, but since bond payments are contractually fixed, they are invariant to the state of the cycle. Only newly-issued debt costs are affected by current interest rates. 

The only way that interest payments would be considered non-structural is that a steady-state interest rate is calculated, and this deviation from actual is used to determine the effect of the cycle. Based on the IMF document, this was not done in their methodology (on page 7, the author states that the only expenditure adjusted was  unemployment benefits). Realistically speaking, such an adjustment would be complex (how much are 10-year bond yields affected by current conditions?), and the effect is small in most countries (since the bulk of outstanding debt has long duration in most countries).