I've found all alternatives and wonder which one is grammatically correct?
- I should have never told you that.
- I should never have told you that.
- I never should have told you that.
It's a matter of style. While I prefer saying/writing 'should never have...' others (like TRomano) may prefer 'never should have'. And neither makes it a wrong choice.
Google NGram shows results of all those three styles, 'should never have' being most frequently used.
Google results of news on the usage 'should never have'