DLP based crypto systems with multiple independent generators
It's not impractical.  Choosing a random generator $g$ is easy and can be done efficiently.  It's efficient enough that it wouldn't be a problem to generate a random generator when you generate your keypair.  I think your premise (your assumption that this is a problem or that it should be discomforting) is not valid.  Consequently, I don't see the relevance of the question.
Let me elaborate a bit.  There are two kinds of values that might be floating around:

Domain parameters are parameters that are shared by many users.  For instance, in a discrete-log based cryptosystem, if the modulus $p$ is shared by everyone, then it is a domain parameter.

Individual parameters (to coin a term) are values that are used by a single party, and are generated by the same party who uses/relies upon them.  For instance, a user's private key is an individual parameter, since it is generated by that user and only used by that user.


These two different kinds of values have different security and verifiability requirements:

Domain parameters are critical and particularly sensitive, since they're generated by one person (e.g., a CA or trusted authority) but used and relied upon by everyone else.  If the CA secretly and dishonestly constructs a domain parameter in a way that introduces a backdoor (rather than following the algorithm they were supposed to use), everyone loses.  That's very bad.  The standard mitigation is to provide everyone a way to verify that the CA generated the domain parameter honestly.
In summary, domain parameters must be verifiable.

Individual parameters don't have this problem.  There's no reason for Alice to secretly embed a backdoor in her private key, since the only person's security who is harmed is Alice's (at worst others may obtain the ability to eavesdrop on messages encrypted to Alice, but a malicious Alice could always have achieved a similar effect simply by publishing all the messages she receives, and there's no way for others to verify Alice hasn't done that).  There's no way for Bob to verify that Alice has kept the messages he sends her secret.  Therefore, there's no reason why Bob would need to verify that Alice generated her private key honestly.  For instance, we don't require that RSA provide a way for Bob to verify that Alice generated her RSA secret key using the algorithm she was supposed to use; if she does something different, we say it is her tough luck.  There's no point in trying to prohibit what you can't prevent.
In summary, individual parameters do not need to be verifiable, and there's no clear value to verifiability.


This means that your question is based upon a faulty premise.  Your premise is that there's something wrong with a cryptosystem if the public key (an individual parameter) is not verifiable.  This premise is not accurate; actually, there's nothing wrong with a cryptosystem where the public and private keys are not verifiable by third parties.  We use cryptosystems like that all the time.  Therefore, the best answer to the question is to un-ask the question.
I am making numerous assumptions about what you are asking.  I confess I might not have understood what you really wanted to know, and what problem you are trying to solve; if so, my apologies.