How to find max margin for non-separable SVM?
Map all the points to the new space.  Then find the maximum-margin linear separator of those mapped points.  Algorithms for finding a maximum-largin linear separator are described in the literature on SVMs (that's exactly what you need to do to train a linear SVM).  In other words, you can map the points to the new space, then can take those mapped points and train a linear SVM on them.  That's conceptually how to do it.

In practice, nonlinear SVMs use clever tricks to do the same thing, but do it faster (using the kernel trick).