Is it bad to have a large gap between training loss and validation loss? Say my training loss is 0.5 and my validation loss is 2.5 (both have stopped decreasing, validation loss never increased). I am clearly overfitting. If I add regularization, my training loss becomes 1 and validation loss 3.5.

The first model clearly has better validation loss, and the second model overfits less.

Which model should be selected? Is it even possible that a model that overfits more performs better on unseen data or does this mean that there is data leakage of some sort?

The problem here is that I'm not doing simple things like image classification but trying something more complicated and I'm not finding a lot of resources on overfitting on problems that have not yet been solved. Mostly it's disussions of binary image classification where it's possible to find models that get a very good validation error, so the explanations don't apply to my problems.
A model is said to be overfitting if there exist another model or hypothesis that has a higher error on the training set but smaller error overall. A model that overfits fails to generalize on out of sample examples. 

In your case, having a much higher error loss on test set could not be a good sign. If you were to chose between the two models I think you should go for the second one, because the first one will probably fail to generalize.

Make sure your training and testing data are picked randomly and represent as accurately as possible the same distribution and the real distribution.

You could do more things other than regularization if want to reduce overfitting, you could try cross validation, or may be reducing the complexity of your model if possible (it depends on the model you training and the data you have)