This was a very very common problem back in the seventies because manufacturers figured out that they could retard the ignition and cam timing; richen the mixture, use an egr, and get the new cars to pass smog. Many a 350 chevy was getting 6-7 mpg in chevelles and novas. Carbon buildup was so bad that people had to shut their engines off in gear or they would just sit there and diesel. I saw some that would continue to run even while in gear. Back then everybody knew you had to pump the gas to start them even moreso hot than cold. They were clogging the cats right and left. Trick we learned quick was to put your hand over the exhaust and feel the pulsations to figure out if it was clogged with carbon; it it just felt like a blow dryer; it was bad. Starters and battery cables were frying like crazy. And they always made that sound; like the motor was fighting against itself to crank over; just like you stated. If you had an oxygen sensor it would be reading very rich. I bet you have to rev the motor sometimes to cure a rough idle. And I bet your plugs are black and sooty.