One from the actual writer: a few years down the line, it occurred to David Gerrold that he could have written Cyrano Jones as a 'barmy old cat lady'; an elderly character who loves tribbles, thinks everyone should have a tribble, and doesn't see that you can have too much of a good thing. And if he had written the character like that, the perfect casting would have been Boris Karloff.
In the same vein, the silent film legend Harold Lloyd was a massive Trek fan in his last years. He'd retired 20 years earlier, but if the production team had heard about that and sounded him out for a cameo, I bet he'd have done it in a shot (elderly but revered admiral maybe? Like the Admiral Quinn character in TNG season one).
Some names from Inside Star Trek's reprints of the Spock Replacement Casting Memoes: Edward Mulhare, Michael Rennie, Dvid Carradine, Curt Lowens... presumably the producers thought they might just be available within Trek's budget with a bit of luck.
Various actors who hadn't quite made it big, or were just coming off TV series and might have been available, or had appeared in Twilight Zone or Outer Limits a little earlier: Jack Nicholson, Charles Bronson (Klingon? A more brutal one), Jean Marsh (alternate choice for Edith Keeler maybe?), David McCallum, Darren McGavin (maybe already a bit too big, but his wife did Trek...)...
Oh, and if Phase II had gone ahead as a TV series, it would have been during Ian McShane's first stint in Hollywood, when he guested on Fantastic Journey and the like. He'd have been a shoo-in for the Byronic lead guest spot in Lord Bobby's Obsession.