How to evaluate data capability to train a model? Bioengineering data comprises of 512 binary features and a single Boolean label: if the particular mixture is worth further research. There are about 1,200,000 results of previous experiments available.

Every "physical" test costs, so it is tempting to train a model to predict if a certain combination of features is worth real testing.

I tried a few models, all failed to render better accuracy than 52% on test data, which is very close to blind guess considering binary classification. Namely, a Feed-forward Multi-layer Perceptron, Random Forest, Naive Bayes models.

For a plain simple XOR example from ML starter courses, for two binary inputs, all 4 cases are required to train the network.  

1.2 mln samples are, perhaps, still a too small dataset to train for 512 inputs, considering a 512-bit number of all combinations and complex cross-influence.

Thinking from the opposite, how to prove that it is impossible to train any model given available training data?
1.2M is about 2^16.
You have 512 features plus the concept so the number of possibilities is much larger.
Therefore, you can claim that the number of samples you have is too small.

Though that, machine learning is done almost always in a situation that you have less samples the all permutations.

The VC dimension allow estimate how well a data set fits the underlying distribution. It applies to an hypothesis class (e.g., linear functions) whose size is typically much smaller than the number of permutations.

Note that both the number of permutations and the VC dimension refer to worse case scenarios. It is possible that on of the 512 is identical to the concept. In this case you will be able to learn though the other 511 features.