GM problem change the solenoid. check to be sure that the exhaust is not leaking on to the starter. worse case scenario is put a remote solenoid on it off a ford or chy. this was the standard fix for the grain trucks. they would be going slow in the field and working all day the solenoid would get hot and the starter would not spin fast enough to start the truck. the remote ford solenoid did the trick. but in your case. you have changed everything else. 4 gage wire is sufficient for the 12 volt system. it's juns not getting the juce threw to the starter motor.
Ed thanks for the reminder...Back in my racing days we ALWAYS ran a Ford solenoid mounted on the firewall to start our hot engines. It's pretty common in racing circles.