pulling the starter to have it checked won't help, it spins fine when cold, you can't pull it hot and keep it that hot all the way to the parts store and onto their tester. They will test and tell you it is fine!
You didn't say, but do you have headers? A Common issue on small block Chevy (especially with headers) is exactly as you described. As suggested above, verify again all your battery cable connections are clean (both ends) You can try a new starter, or a mini hi torque starter but, as Jerry suggested above, verify battery is good, check voltage while cranking (check hot and cold and note the difference). I think you will find, your battery voltage is dropping quite a bit when starter is hot. You might also find that a heat shield (just a piece of sheet metal) between exhaust and starter will help greatly.
