I'm going by the
Japanese Wikipedia article, and my understanding is that the prefectural police where he lived would be the appropriate contact point. The other procedure (going between embassies) is listed, but seems to be specific to immigration/visa cases.
If you would tell us where you lived, I could probably Google the appropriate police and contact information for you. I noticed in my Google results that there were pages from several prefectural police departments regarding issuing this criminal background report.