I have managed to get a few Gold Chocobos before, but it is very frustrating. The farthest I got with Tifa was a Black Chocobo, but I've never gotten a gold chocobo without Cloud. Is it just extremely rare to get a Gold Chocobo with C class chocobos or impossible?

The earliest I recall getting Knights of the Round was right before Midgar, which is when the official guide first suggests that strategy.