Cluster analysis as an associative model?
I think the question you're wrestling with is essentially this: Is there a way to use information that may be present in the data without A as part of your strategy for predicting A?  There is actually a name for the set of methods that do exactly that: semi-supervised learning.  

While there are multiple techniques, a method analogous to what you suggest in your question would be something like the following.  Here I refer to the set of data with A as labeled and the rest as unlabeled.


Apply an unsupervised learning technique (such as clustering) to the full data set (both labelled and unlabelled).
Transform the labelled data based on the result of your unsupervised learning technique.
Apply a supervised learning technique with the transformed set (possibly combined with the original set) of labelled data.


Generally you would want to apply a cross-validation strategy as well to detect overfitting.