Ensure of features relevance / Ensure of feasablility of a prediction I have a set of features and a target(labeled data). I want to classify this labeled data into several classes. I've used many algorithms in a benchmarking approach but none of them seems to give a good result.
Knowing that I have used PCA/Factor to perform a features selection and as algorithms I used SVM, C5, CHAID, Bayesian Net. and Xgboost. 
My question is: How can I be sure that the features I'm using can predict the target ? When can we stop and say: "it's not possible to separate the classes using these parameters/features ? 
 A: Situation 1 : You want to fit your training set
Imagine that $x_i$ and $y_i$ are feature and target vector respectively for $i=1,\ldots,n$ observation pairs then if there's $n$ unique feature vectors you can perfectly fit your data with $n$ indicator functions... So stop when this is done.
Situation 2 : You want to build a predictive model
Try to imagine this question in a situation were you are randomly simulating feature $X$ and target data $Y$ $\sim (X,Y)$ i.e have infinite amount of data. 
You want to find a function $f$ i.e your model minimizing some loss function $L$ which I assume is cross entropy. Since this should be minimized for new data what you want is to
$$\min_f E\left[ L(Y,f(X))\right]$$

How can I be sure that the features I'm using can predict the target?

With infinite data I assume you could fit this by using some infinite amount of basis functions to recover the predicted quantity your interested in. As an example say you have $K$ predictors and want to predict the bernoulli parameter $p$ for a binary prediction task then you could do this with logistic polynomial regression or more intuitively set
$$\hat{p}=f(x)=sigmoid\left(\sum_{i=0}^{\infty}\sum_{k=1}^{K}\alpha_{ik}X^i_k\right)$$ 
should do it. (I'm sure there's better examples)
If you see that $\alpha_{ik}=0$ for $i>0$ the correct model is a baseline model then you can conclude that your features can't predict the data.
You don't have infinite amount of data. In particular your test set is not infinite so being frugal with this essential to ensure you're estimating the expected error. This leads to be relying on best practices and domain heuristics about how high AUC$^{***}$ or some other ROC-metric can be for similar problems.
All models you mentioned are bagging basis functions based on such heuristics and it usually works well.
I think all good answers to this question should focus on what the best practices are. I think one important such on this type of open prediction problem is to plan ahead how the test set will be used. 

When can we stop and say: "it's not possible to separate the classes using these parameters/features ? 

When you've depleted your testing data
$^*$Accuracy is a useless metric and should never be used unless you have equal class prevalence
A: I agree with you that having data is different from having information, you could have all the data in the world but if it doesn't suit your problem you are unlikely to have information.
But in this case it seems you are insisting too much on the data quality and not listening to what is being said in the comments.
Prediction with an imbalanced dataset is a tough problem, one that needs to be dealt with, that could also be your problem.
If what you said is true and only 0.4 % of your classes are positive then you likely have a problem at hands.
I am surprised that you didn't have 99.6% accuracy, that would surely be the verdict if you used a NN or Log regressor (they tend to get very stuck in local minima in those scenarios), and that surely wouldn't be a good result (always output negative).
I would try either oversampling from the minority class or undersampling the majority class before taking any conclusions about the quality of the data (just to make sure). (I had more success with oversampling the minority)
Check if that makes any difference on the performance of your classifier.
Also, it might be a good idea not focus on accuracy but on the precision and recall.. in this kind of settings (highly unbalanced) accuracy has really no meaning.
A: Let say that you have 10 features, what you can do is:

*

*start with all 10 columns, train your model and see what's your
result (eval metric: AUC, AUCPR, ... depending on your case).

*Loop over all your columns, remove the current, retrain and see if that makes a negative effect on the evaluation metric. If it
does, then it has some relevant information in it, if it doesn't
then it has no predictive power and you can just discard it.

*At the end of your exercise, if all the columns are discarded, then your data might not contain anything useful in regards to your target.

