In theory could a pubkeyhash script be solved without the public key in the scriptSig? When signing a pubkeyhash UTXO, it is required to provide both a signature and a public key. The public key is duplicated and one copy is provided to op_checksigverify to ensure the signature is valid, and the other copy is hashed to ensure it matches the pubkeyhash. 

In theory, is it possible to build an opcode like op_checksigverify_pushkey that takes only the signature of the transaction and extracts the public key from the signature? With this it would be possible to only specify the signature and no need to provide the public key. The public key of course could be arbitrary, but would fail when hashed and compared against the vout pubkeyhash.
It's possible, but:


It's much slower
Pubkey recovery for this kind of application is arguably patented


For a "signature only" scriptpubkey, we already have p2pk.  Hopefully in the future, segwit programs will have bare pubkeys in the scriptpubkey, allowing for similar (and more advanced) constructions.