Turns out I was wrong with this game too. In the Japanese version the ending only depends on the number of continues you have used. I got the second worst ending.
I didn't use a walkthrough or guide, one reason being that I thought they were inaccurate, another reason that the guides lead you to the perfect NES ending, but also because I enjoyed the game too much to care about walkthroughs. I got stuck first at level 3-2, until I found a little glitch in the beginning that makes the first witch drop down, and then finally got lucky and got through the initial hard part. The theif enemies had stolen my crossbow and that made the first part much harder. I think next time if enemies steal my item, I will just kill myself to restart the level.
The last castle (3-4) was quite difficult too because I kept getting eggplanted, and couldn't find the boss room. Then I died with only 11 hits left of him, and again with 14. But alright, it's done, and it was a pretty fun game! That's the fourth Famicom game I beat.
I now want to buy all Kid Icarus disks I can find to see what their high scores are and try to beat the game.