If your data isn't governed by an underlying law involving regularities (which seems to be the case in your example), Knn is indeed what makes the most sense, and linear methods (Gaussian modeling, regression, etc.) won't help you.

The best is to use nonlinear methods. You could try using a random forest method. Decision trees create a tree structure that delineates areas and identifies clusters. You just need to limit the number of parameters to avoid overfitting (like max depth or min samples per leaf), especially on ambiguous data like the one you've shown.