In The Revenge of Shinobi, the prequel to Shinobi III, you play as a ninja (what else?) who is capable of destroying an entire army of other ninjas, soldiers, and Hollywood characters. The fast attack animation of the ninja (one of which throws fireballs everywhere) makes up for his lack of speed.
In this run, CoolHandMike beats his original attempt by 00:01.22 seconds thanks to better optimization.