The game becomes a lot easier as you level up, the skills available make combat against large numbers of enemies much easier. I found it relatively easy to take on large groups without to much trouble by the time you get to the second part of the map.
That said you have to be much more tactical early on, taking out captains and large groups is suppose to be tough. Remember that there is no penalty for death (other than the captain's level increase) you actually get a 100xp bonus and it creates rivalries for the nemesis system thrive so don't be afraid to take some risks.
Try to identify easier targets by gaining intel on each captain and knowing weaknesses such as fear of beasts, vulnerable to fire / explosions, stealth finishers, etc. and exploit them by sneaking around and striking at the best moment.
This could mean stealthily following a captain until they are close to something they are vulnerable to and using and arrow to shoot a cage door or explode a barrel then jumping down to finish them off before too many uruk arrive.
Also worth bearing in mind is that if the captain is vulnerable to ranged attacks you can often take large amounts of life by effectively using the focus skill to slow time and get head shots.
Before going in for the kill you should know what will and won't work in close combat, some captains require you to wait for a chance to counter or are immune to combat finishers.
As for healing there are again skills and runes available in mid to late game that give you healing for doing specific actions during combat but they are no good to you at this point. Running to find a herb is your only option.
All out brawls with numerous uruk or more than one captain should be avoided at all costs until later on.
Get intel and exploit weaknesses from positions of stealth then drop in and finish off captains. Avoid large groups of enemies until later.