OK, it seems to work for me. Here is what I did:

_ Unzip using 7zip. Igonre CRC errors.
_ Downloaded HxD for hex editing.
https://mh-nexus.de/en/hxd/
_Check this for editing reference (not just the first post, there is more info later)
http://heroescommunity.com/viewthread.php3?TID=18817&pagenumber=1

In the example you gave me I found Terek. Let's try to change his secondary skills.

Open the file in HxD and find the string "Terek". See attachment.
_ The hero's name is stored in 13 bytes. These are the bytes highlighted.
_ The next 28 bytes represent his secondary skill. These are the bytes in grey brackets. 00 means none, 01 means basic, 02 means advanced and 03 means expert. For order of skills refer to the thread above.
_ Note the 8th byte (underlined in red) which is Basic Wisdom and 20th byte (underlined in green) which is Basic Tactics.
_ The next 28 bytes show which secondary skill appears in which slot. A value of 01 means the skill is in first slot, 02 means skill is in second slot... etc.
_ Note the 8th byte (underlined in light red) which is Wisdom has a value of 01 (first slot) and the 20th byte (underlined in light green) is Tactics which has a value of 02 (second slot).
Putting more than one skill in the same slot or into invalid slots might lead to unwated effects or crahing.

So let's try to give Terek Leadership. That's skill #7

Step 1:
Change the value in orange box to 01 for Basic, 02 for Advance and 03 for expert.
Note: you can stop here, in which case the leadership skill will not appear in the hero's skill screen, but you will still get its effect (you can see morale increase). In fact you can get the expert effect of all 28 skills, even though only 8 will appear in the hero's screen.

Step 2:
Change the value in black box to 03. This means the leadership skill will appear in the 3rd slot.

Step 3:
Note the value 02 in the pink box. That box is located at -126 offset from the beginning of hero's name (i.e. 126 byte before the beginning of hero's name). That's where the total number of active skill slots to be shown is stored. Since we added a third skill, change that value to 03.

You can do other changes. Those FF's at the bottom for example are where artifacts are stored. FF FF FF FF means empty. Note the 62 00 00 00; those are the boots of speed. Again, check the thread for reference.

Next, you have to re-zip the edited file. You can do it in 7zip, but you must change archive type to gzip. See attachment.

And you're done. You can load the game, and Terek now has a new Leadership skill.

Try experimenting using the reference thread I posted. I'm not an expert on Heros save editing, but if you need any help, give me a shout and I'll see what I can do.
...