In theory could a pubkeyhash script be solved without the public key in the scriptSig?
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.