A boatload of cash, and a patience for resets until you get it. Twelve resets isn't enough.

Alternatively, you can try to boost his affection rating by getting successive Wakizashis, which are the only things that boost his rating. Daigoro reduces it, and Kozuka does nothing. You could get one or two Wakizashis, save, and continue; reset if you get anything less than Kozuka. Over time and through this method, Zanmato should appear eventually, even if accidentally.

Once you actually get Zanmato, it becomes slightly easier the next time (Zanmato improves the affection rating). Depending on the version, it will be harder (NTSC, NTSC-J) or easier (PAL, Int'l).

As far as I know, Overdrive doesn't do anything. The only notable difference I've seen is that it makes Kozuka and Wakizashi attack all units on screen. I personally have never gotten Zanmato on Overdrive.