Your best bet will be to use Guns, axes, and samurai swords as they offer the best damage possibilities in the game. Axes do random damage (sometimes 200 sometimes 5000), guns ignore enemy defense, and Katanas have the highest multi-hit factor.

The main problem you may face is the fact that damage is factored by other stats depending on your weapon. Knives and Ninja blades use your speed stat while poles use your magic stat. Other weapons also have to factor in enemy stats. This is why I chose the three above cause the sorta get around these obstacles. You will probably need guns for the beginning until axes become available then I would just stick to them.

I don't know if this challenge is really possible I'm afraid. I don't particulary care for speed and low run challenges, much like Skyblade.