tl;dr
The safest method I've found is to use cross-validation for hyperparameter selection and a hold-out test set for a final evaluation.
Why this isn't working for you...
In your case, I suspect you're either running a large number of iterations during for hyperparameter selection or you have a fairly small dataset (or even a combination of both). If you can't find more data or use a larger dataset, I'd suggest limiting the exhaustiveness of your hyperparameter selection phase. If you run the process enough times the model is bound to overfit on the validation sets.
Note that there is no guaranteed safe way of detecting overfitting before the test set!
Why I consider this strategy to be the safest
There are two different types of overfitting you need to be able to detect.
The first is the most straightforward: overfitting on the training set. This means that the model has memorized the training set and can't generalize beyond that. If the test set even slightly differs from the training set (which is the case in most real-world problems), then the model will perform worse on it than on the training set. This is simple to detect and, in fact, the only thing you need to catch this is a test set!
The second type of overfitting you need to detect is on the test set. Imagine you have a model and you make an exhaustive hyperparameter selection using a test set. Then you evaluate on the same test set. By doing this, you have adjusted your hyperparameters to achieve the best score for the specific test set. These hyperparameters are thus overfitting to that test set, even though the samples from that set were never seen during training. This is possible, because, during the iterative hyperparameter selection process, you have passed information about your test set to your model!
This is much harder to detect. In fact, the only way to do so is to split the original data into three parts: the training, the validation and the test sets. The first is used for training the model, the second for hyperparameter selection, and the final is used only once for a final evaluation. If your model has overfitted (i.e. test performance is worse than training and validation), you need to start from scratch. Shuffle your data, split it again and repeat the process. This is usually referred to as a hold-out strategy.
To make the model even less prone to overfitting, you can use cross-validation instead of a hold-out validation set. Because your model now has to be trained on $k$ slightly different training sets and evaluated on $k$ completely different validation sets, it is much harder for it to overfit on the validation sets (because it needs to fool $k$ different validation sets instead of one).
Cases where this might not be applicable
Depending on the circumstances, it might not be practical to apply both of these techniques.
Cross-validation is pretty robust regarding overfitting but it imposes a computational burden to your process as it requires multiple trainings of the same model. This obviously isn't practical for computationally expensive models (e.g. image classifiers). In this case, use a hold-out strategy as mentioned previously.
Using a hold-out test set means that you are reducing the size of your training set, which might actually make your model more prone to overfitting (i.e. have a higher-variance) for small datasets. In this case (if your model is practically untrainable due to the small size) you can resort to cross-validation, but you risk overfitting on the validation set and not having any way to detect it.
How to combat overfitting
Since it is fairly related, I'll post a link to an answer on how to combat overfitting.
