The "Leader title costumation" at the beginning of a new game only works for the tribe you start with, I think, but this should be sufficient in most cases. I haven't used this feature for ages, though, so I might be wrong.
If you want to change them for all Civs, there seems to be no way around changing the titles given below "@GOVERNMENTS" in the rules.ger file, which is straightforward to adjust.
However, if you want to have individual leader titles different for special civs, Civ2 shows a very strage bug, described by Gothmog at
http://members.xoom.com/fambans/index.html
(with a way to fix the problem)