It is easily possible without immortality by switching warrior lodges. In my Indo-Norse campaign, I have a (Germanic) ruler who completed the legendary journey for both the Bon and Tengri warrior lodges (and got a bloodline for each). (The Germanic warrior lodge was on cooldown thanks to the previous ruler.) His eldest son also got a bloodline for the Bon legendary journey.
The only disadvantage of being in a wrong-religion warrior lodge is that some decisions are unavailable (eg. battlefield sacrifice, "toughness" for Bon). Also (and this is probably a bug), the Tengri bloodline didn't propagate properly to all of my descendants - including the one I wanted as my heir. Also also, you lose the viking/ravager/sea king trait when you switch religion.
Even if you don't go for two journeys, it's highly worthwhile to switch warrior lodges - you can collect all of the commander traits and end up with bonuses to just about everything.
Basically, you need a very young (16-20) and fairly militarily-capable ruler. Preferably "strong" (you can pick up brawny later) and with a military education (for the small +health bonus at level 4). (EDIT - You must
not be zealous.) Join a warrior lodge. Advance as quickly as possible and trigger the legendary journey. If you're quick, you should be finished by the time you're 50ish. Make sure you have about 1000 prestige and piety. Leave the warrior lodge. Get a concubine of a different (pagan) religion. Wait 90 days (so you can join societies once more). Use your concubine to change religion (EDIT - requires non-zealous) (right-click on her, choose secret religion, right-click on yourself, openly adopt faith). Apply to the newly-available warrior society. (Optional: Once you have completed your duel and become a member, switch back to your "real" religion - eg. by right-clicking on yourself and "adopting capital county religion". You won't be kicked out.) Once again, advance as fast as possible. You should be able to finish the second legendary journey by approx age 80. (This is why you need all of the +health you can find.)
I don't know if this requires the 3.0.1.1 beta for the legendary journey fix. But it's probably best to upgrade, just in case.