As a start, think of your melody notes as chord tones. Not a group of them at once, but each individually.
For example, if the note is a G, then the chord should have that G. It doesn't need to be G major or minor; it could be C major (C E G) or minor (C Eb G). Maybe E minor (E G B).
And not every note needs to fit, as long as they're not too jarring. If there's a G and a B, go G major instead of G minor.
There could be a temptation to go fully diatonic: all the notes on the melody are in the C major scale, all the chords are C, Dmin, Emin, F, G, Amin. This is appropriate for country or folk, for example, but in jazz, you are encouraged to vary wildly from this. I don't know the stylistic standards for J-rock (I have passing familiarity with Shonan Knife and the Boredoms, but figure that's a generation away from your desired sound).
Best of luck!