MOV datasheets typically provide a plot of expected lifetime versus current or energy, with an asymptotic infinite life curve given. Relay coils store very little energy as surges go, and even a SMT chip MOV should do fine.
TVS vs. MOV doesn't really mean anything: if you're depending on the higher voltage drop of the MOV, you can just choose a higher rated TVS. The TVS will give a squarer flyback voltage, giving slightly shorter discharge time for the same peak voltage.
Tim