Wikipedia: Labours Of Hercules
Granted, Hercules could not have provided the video documentation necessary for badge approval. I'm confident that the approval board would waive this requirement, especially given Hercules's known habit of killing most anyone who got between him and his goals.
However, there are two badges that Hercules would clearly fail to obtain. The Augean Stables were cleaned by bringing in off-site materials (the rivers Alpheus and Peneus), thus violating the Local Materials requirement. Part of capturing the man-eating Mares Of Diomedes involved feeding them the flesh of their owner, King Diomedes. As Hercules did not show that Diomedes's flesh was Organic Or Better, the badge would be refused.
It is interesting to note that Hercules was not able to do SKIP work on the property owned by his parents. Luckily, his Labor Taskmaster (King Eurystheus) provided a number of SKIP properties for Hercules to use. Six of these were nearby, as shown on the map below.