There is also the "masked hero" who wears a mask (and often hat and cape), but is otherwise dressed in regular attire. The Shadow would be the first of these unless you count Zorro, followed by his fellow pulp imitators like the Spider and Blask Mask. In comics the first masked hero would be the Clock. Crimson Avenger would fall into this category, as well as Sandman in his original costume.
Calling Mandrake and Flash Gordon costumed superheroes is probably reaching a little bit. Flash Gordon doesn't wear a costume, just normal clothes for Mongo, and I don't recall him being stronger - are you sure you aren't thinking of John Carter? And Mandrake's stage outfit is still just a tophat and tuxedo - kind of a stretch to call that a superhero costume. The Phantom is the first character to wear what we think of today as a traditional superhero costume (i.e. mask and tights), but he had no special powers.
There is no doubt that all these characters were precursors to the superhero,along with Tarzan, Tracy, Doc Savage and even Popeye, but the total package doesn't come together until Superman.