A few examples (bearing in mind that should've is pronounced shoulda /'ʃʊɾə/;
ungrammatical sentences are marked with asterisks, as usual)
- Never should I have done it.
- I never should've done it.
- I should never have done it. ~ I should never've done it.
- I should've never done it.
- *I should've done it never.
- *Not should I have done it.
- *I not should've done it.
- I shouldn't've done it.
- I should've not done it. ~ I should'ven't done it
- *I should've done it not.
Note that both never and not are negatives. Already is not a negative.
- *Already should I have done it.
- I already should've done it.
- I should already have done it. ~ I should already've done it.
- I should've already done it.
- I should've done it already.
- negatives can't go last, but adverbs like already can.
- never and not have different distributions.
- negative adverbs like never can optionally front and invert the subject.
- adverbs (and negatives) can go after the first auxiliary verb
To answer the question as posed, the reason the word order is different in the two example sentences is because that's the way the speaker said them. They could have said those sentences differently without changing the meaning or being ungrammatical.
Most adverb placement is speaker's choice -- you put it wherever you feel it should go best, for whatever reason. You're gonna be saying something else in a few seconds, after all, and this is just an adverb. Nobody cares what order it's in as long as it gets out fast enough. That's why I used contractions above -- the way people talk is not the same as the way they're taught to write.