Is it bad to have a large gap between training loss and validation loss?
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)