Issue while predicting multiple values which possess different order of magnitude (regression)
I am maybe thinking about creating one loss per target. Freeze all the
  network except the output layer and each epoch let one of the loss
  train the whole network. But I am not sure it is a good idea.


This is one option. It should work but it may be slower to converge as you only make use of only a third of your losses each epoch. Also, it is not completely unlikely that your losses may work "against each other". Meaning that they could somewhat cancel each other out, which can make convergence take longer.


  Currently I am normalizing the target before predicting it, but I don't like this solution very much. I would prefer having a slightly more complicated architecture than normalizing and denormalizing (afraid of data leakage) and it seems more robust to directly output the right value.


That's what I would do. I don't think you should be afraid of data leakage. Computers have enough precision in them that normalizing/denormalizing shouldn't create any issues. Also, keep in mind that computers have greater precision for floats close to 0. So normalizing your data may actually be good.

And when you say, I'd rather directly output the right value. You can do both! Your network could directly output the denormalized value, but the loss used to train the network can be computed on any layer before that.