One-Class discriminatory classification with imbalanced, heterogenous Negative background?
One class learning

I wouldn't be too quick to throw out one-class classification methods (option 2) - the key is to model the positive (minority) class with the one-class model.  

There has been research demonstrating cases where one-class classification out-performed other approaches like sampling for highly imbalanced data as often seen with protein classification tasks.

I couldn't find the research I recalled, but I did find some other comparisons, showing using one-class classifiers (typically modeling the minority class) achieved as good or better performance than binary classification typically with sampled "negatives" from the large set of proteins not known to be positive.  

Additionally this approach also gives the advantage of much improved run-time - since you only need to train the classifier on the smaller, positive set.  A couple papers:

"Prediction of protein-protein interactions using one-class classification methods and integrating diverse biological data"

"A One-Class Classification Approach for Protein Sequences and Structures"

At the very least I would try some one-class methods and compare the performance using validation with your binary/multi-class classification approaches.  There are also open source implementations for many of these so it shouldn't be too costly to try them out, for example LibSVM has a one-class SVM implementation.  Additionally, it might prove valuable for use in an ensemble with binary classifiers, since there may be more disagreement in their predictions.

Higher level representation embedding / clustering

Along the lines of what you were thinking with (1) and the other post suggesting PCA, approaches like clustering, sparse coding, or even topic modeling - treating each protein as a document string and different protein families as different topics - could yield a representation that might make classifying the proteins straightforward.  

I.e., you could identify which group/cluster a protein belongs to or classify the cluster memberships / embedded representations.  

E.g., such embedding approaches as sparse coding can yield representations that reveal which cluster a protein belongs too - so that some sets of features are only active (non-zero) for proteins in the same cluster - which can make classifying them much easier. 

Additionally class labels or known cluster membership can be incorporated in the embedding process for most methods.

Ensemble

Ensembles of multiple classifiers tend to work best - especially when the classifiers are very diverse and can achieve comparable performance individually.  

There are at least two ways use ensembles for this problem.


You can build an ensemble of binary classifiers by sampling multiple different same-size negative sets and training a classifier on each.
You can build an ensemble from different approaches, such as binary classifiers with different negative samples, combined with a one-class classification approach, combined with classification models trained on the embedded data.