The way to solve that is to introduce a different form of service to the state along side with military service so that the choice in practice become the same.

Is there anything in the constitution that forbids the government from requiring citizens to perform some kind of service to the government?