The NPC that bags shinobi-tabi for you is in whichever country is in first for that week. He travels with the travelling circus.
If Bastok is #1
Ominous Cloud Bastok Port L-8
If San d'Oria is #1
Ominous Cloud San d'Oria South H-9
If Windurst is #1
Ominous Cloud Windurst Woods H-10
Just trade him as many as seven stacks of tools at once, along with the corresponding number of winjruit.