For the time being, Heyman should just stick with Brock until someone comes along who seems like they would have great chemistry with Heyman. Just slapping anyone with him won't work seeing as how Curtis Axel and (Heidenrich years ago) were both busts. I didn't find the Ryback pairing bad at all, he was just paired with Heyman at the wrong time, i.e. in the middle of the Punk/Heyman feud when anyone associated with Heyman not named Brock was gonna be jobbing to Punk, and more jobbing was exactly what Ryback didn't need at the time. At any other time, Ryback becoming a Paul Heyman Guy could have actually been beneficial to him.
Some have suggested before that pairing Heyman up with a Diva could be a good idea, but that's an absolutely terrible suggestion imo. Few people care about the Divas at all and it would be such a waste of Heyman to try and use him to get someone in such an irrelevant division over.
I'm also against the idea that only someone with sub-par mic skills should be paired with Heyman. I know it worked well with Lesnar (and still does) but Rick Rude and Mr. Perfect were both more than capable of handling things on their own on the mic but it was still a good idea to pair them up with Bobby Heenan. Same goes with Flair when he and Heenan (and Perfect) were together in '92. It's all about finding someone who would click with Heyman perfectly, whether they can talk on their own or not.