Not a native speaker, so take this with a grain of salt. :)
First, let's look at your bolded piece.
I came across two possible interpretations of this phrase. The first is where I first landed, until I found an unexpected wrinkle that led to the second.
If memory serves, in Old and Classical Japanese, the 連体形【れんたいけい】 or "attributive form" can be used as a substantive (basically, a noun) in certain constructions. In your sample sentence, we see 足りぬ immediately followed by を探し, suggesting this kind of grammatical construction.
- If we parse 足りぬ as the 連用形【れんようけい】 tari- of verb taru, then the ぬ must be the spontaneous / unintentional perfective auxiliary. That doesn't quite make sense in this context. The 連体形 for perfective ぬ is ぬる (see entry at Kotobank), but we don't have that here. Considering the grammatical structure, perfective ぬ doesn't fit.
- If we parse 足りぬ instead as the 未然形【みぜんけい】 tari- of verb tariru, and consider the grammar, then the ぬ must be the 連体形 of the negative auxiliary ず (see entry at Kotobank).
- We also find that the verb form 足【た】りる arose in the Edo period (see entry at Kotobank, scroll down to the section for the たりる reading), which would work for a period drama.
⇒ The phrase 足りぬを探し then works out to something like "looking for gaps / lacks / places where something isn't enough", alluding to a search for self-improvement or possibly for justice. Depending on the show's context and the character that speaks this line, this might be the intended sense.
However, apparently there was also a lexicalization (case where a particular form of a word becomes an independent word in its own right) of 足りぬ based on taru → tari- + perfective ぬ, which became a noun meaning something like "satisfaction". The dictionary entry at Kotobank is for the slightly contracted form たんぬ, which apparently arose by at least 1241 (when it is first cited). It's not clear to me if the uncontracted form たりぬ was also in use as a noun with the same meaning.
⇒ If tarinu was also used as a noun with the "satisfaction" sense, then the phrase 足りぬを探し would be hedonistic rather than righteous. Again, depends on the show's context as to whether this is a sensible interpretation.
Let's look at those first three pieces as a clause.
The 足りぬ is treated as a noun regardless of which of the two interpretations we use (righteous or hedonistic). Starting from there, there isn't much reason to tie the 我が道 to the 足りぬ as a single piece. The 我が道に is essentially setting the stage for the rest of this clause: "on my path", "along my way", something to that effect. So it would have to be the second parsing option that you post: 我が道に[足りぬを探し].
I notice that this piece of text is in classical 短歌【たんか】 format, if we make one small allowance:
The mora count is the classic 5-7-5-7-7, if we ignore the 長音符【ちょうおんぷ】 in ビューティフル and only count this as 4 instead of 5.
Noticing that this is poetry, and looking at this as a standalone text in its own right, the moral ambiguity about the potential intended meaning of 足りぬ might be intentional. Is the speaker seeking justice, or seeking pleasure? Either way, they recognize that life is beautiful right at the moment of dying.
Personally, I think Possibility 1 above seems more likely, as this makes the poem more poignant -- in this case, the speaker has been seeking out insufficiencies and fighting against them. If we use Possibility 2, it doesn't make as much sense -- hedonists aren't big on self-reflection, and if someone is so wrapped up in the pleasure of the moment anyway, there's no reason for a last-moment realization of beauty.
Update: Identifying the Nu
"No no no no, no, Sir Bedevere, it's not that, it's Ni!"
More seriously, you can tell which ぬ -- the spontaneous perfective auxiliary, or the negative auxiliary -- based on the form of the underlying verb, in most (but not all!) cases, and sometimes also based on the grammatical context of where it appears.
- Perfective ぬ attaches to the 連用形【れんようけい】 of the main verb.
- Negative ぬ attaches to the 未然形【みぜんけい】 of the main verb.
The challenge comes with verbs that have different overlapping forms, such as たり -- this is both the 連用形 for たる, which is a 四段【よだん】動詞【どうし】 ("four-step verb", since the verb stem ends in four different vowels in Classical and older → this became the modern 五段【ごだん】動詞【どうし】 or "five-step verb"), and it is also the stem for all of the 形 for たりる, an 一段【いちだん】動詞【どうし】 ("one-step verb", since these verbs only have one vowel for all verb stems).
In these cases, you'll have to look more at the surrounding grammar and the form of the auxiliary itself. These auxiliaries also have conjugational forms of their own, which can help you identify what you've got:
Irrealis (hasn't happened yet)
Continuative (-masu stem)
Realis (as if it's happened)
Between these two -- the conjugational form of the main verb, and the conjugational form of the auxiliary -- it is often possible to narrow down which ぬ you're looking at.
That said, as we see above with たんぬ, that is an example of a perfective ぬ in the 終止形【しゅうしけい】 conjugation, but this lexicalized into an independent noun -- where usually only the 連体形【れんたいけい】 could be used that way. Language is nothing if not irregular. 😄