I always want to say 'Jack and Jill both had red hair', but wouldn't 'Jack and Jill had red hair' do the same job?
You are correct. 'Both' is redundant. That isn't to say you shouldn't say 'both.' Redundancy can be used as an effect. Just don't over-do it.
I was about to say it, but Maia took the words right out of my... keyboard? Eh. The word both in this context would only be used for emphasis or inclusion, but you'd definitely have it at the front, not the middle.