It seems that until about a month in I don't have enough troops to split among my heroes, and the only way to clear out stockpiles and explore is to give my strongest hero all of them while other heroes relay new ones to him and meander about near my town collecting resources. If I do split my troops up I constantly find monster groups I can't defeat which hampers my ability to explore.

In summary:
Split troops to defend and explore means each heroes troops are too weak to overcome most monster groups.
Lumping troops to one hero makes him a good explorer, but I then only have 1 explorer, and defense becomes harder.

I do use scouts, but if I have a path blocked by monsters and my main hero is 4-5 days travel away what can I do? I've been told pumping Diplomacy at lower levels and recruiting random troops helps, but none of my heroes ever seem to get it early on.

You can use chaining: Keep your heroes in range of eachother, so that you could pass over the troups from one hero to another and to another and so on to have them in your castle for defence, or at any other place where they are needed.

http://heroescommunity.com/viewthread.php3?TID=39246

What difficulty are you playing on?