Trying to heroquest every year is probably what's causing you problems. Wait two or three years between heroquest attempts. (I'm not entirely sure whether or not two years are enough; three years should always be all right.) If you go to the Quests screen and listen to your advisors, they'll tell you whether or not it's been too soon since your last one; if you assigned magic and they still say it's too soon, just let that magic go instead of trying anyway. By the way, the magic only applies to the first time each year you try to heroquest, so if you get everyone together and can't even get to the Godplane, don't just try again the next season.
Your ring should have representatives of seven different gods, but the most important thing is having someone with high Magic skill: this seems to be what makes the big difference between your hero actually getting to the Godplane and your hero standing in a field wearing a cow mask. I don't know the details, but I assume "excellent" is just the baseline for what skill level your best magician would need, and that "renowned" or "heroic" would give you a much better chance.
The skills of the person performing the heroquest make a difference; it's not just a matter of them worshipping the right god. This isn't something I know enough about to give definitive answers as to what skill levels you need for a better chance of success. The manual says that Combat, Magic and Leadership are the primary skills, but specific quests test specific skills: for example, you'll need to have a good Bargaining skill for the Issaries quest. I wouldn't want to send someone out if they didn't already have "Excellent" in the skills that seemed relevant to the quest, and again that's just the baseline: someone who's already renowned or heroic in one or more skills has a much better chance of succeeding. It's frustrating, because the very people you don't want to lose are the ones you've got to send out. Learn all the myth details and the four myth secrets, then choose your heroquest by who can do the job, not by what result you want.
I don't believe that Mysteries has an effect on heroquests; if it did, it would probably be in the manual, but the manual just says that Mysteries increases the chances of success when you sacrifice to learn mysteries. So you can save that extra point for your magic pool. (If saving up 10 is a problem for you, I'm sure it helps but I don't think you really need that many. Three or four seems to be a strong enough number, though I couldn't say for sure.)
Once you're in a tribe, you can get a hundred or more extra worshippers if you ask for help, though you can definitely do heroquests before then. It may also be worthwhile to pick up the Scarf of Seven Runes through trading for treasures with other clans, and the Magnet of Mostal by exploring until you find Dwarf Valley, then going back to that area.
And, you know, sometimes you just fail no matter what you do. I've had Kallyr die at the very end of Orlanth and Aroka when she really should have made it through. It's completely superstitious, but although I'm in the habit of skimming most screens I slow down and read every bit of heroquest text, even out loud sometimes. This is the most important thing these people can do, and I see all the hoops and attacks of bad luck as the game's way of making the player slow down and appreciate that importance.
I hope that helps!
