If the predicate were 消える instead of 消えない, が would have sounded neutral and 消える would have been understood as referring to a one-time change (that does happen).
君とここまで歩いてきた足跡が消える [one-time change / neutral]
は, on the other hand, would have put 足跡 in contrast with other things as if to say although those other things won’t disappear, their footprints will.
君とここまで歩いてきた足跡は消える [one-time change / contrastive]
Your understanding is more or less correct so far.
However, the predicate in your sentence is 消えない. In general, a negative verbal predicate tends to be understood as referring to a static property of something, rather than a one-time change that doesn’t happen. In this case, は sounds more neutral than が just as is the case with a nominal or adjectival predicate (whether affirmative or negative) which usually refers to a static property.
ボールペンで書いた字は消えない。[static property / neutral]
は also sounds neutral when an affirmative verbal predicate does refer to a static property, although it may still carry a contrastive nuance depending on the context (as when the following sentence immediately follows the sentence above).
鉛筆で書いた字は消える。[static property / neutral]
When が is used with a negative verbal predicate, it takes on an “exhaustive-listing” quality and also the verb is likely to be understood as referring to a one-time change that doesn’t happen. The result is that it sounds like you are specifically stating something doesn’t happen when it is expected to.
Let’s take a step back and look at the following pair with affirmative predicates, where たら more or less ensures the verb is understood as referring to a one-time change in both.
８時になったら電気が消える。[one-time change / neutral]
８時になったら電気は消える。[one-time change / contrastive]
Now, let’s look at the following.
８時になっても電気が消えない。[one-time change / unexpected]
８時になっても電気は消えない。[one-time change / contrastive] or [static property / neutral]
The sentence with が sounds like the speaker is surprised that the lights don’t go off even after eight.
Your sentence is similar to that.
たとえ思い出になってでも 昔の話になってでも
君とここまで歩いてきた足跡が消えない
It almost sounds as if the speaker wants to erase the footprints but they persist. I agree with the commenter. は would sound more neutral and natural.
[Reference]
「初級を教える人のための日本語文法ハンドブック」—§27—「は」と「が」(p265-6)
【これだけは】
＜規則２＞ 述語が動詞以外（形容詞・名詞＋だ）のときは通常「は」を使う。動詞の場合でも次のときは通常「は」を使う。
① 主語が「私」「あなた」（一、二人称）である場合
② 恒常的な出来事を表す場合
③ 否定文である場合
◆ここからは単文における規則になります（なお、複文の主節は単文の場合と同様に考えることができます）。まず、最初の規則は文の種類によるもので、単純に言うと動詞文以外では「は」を使うということになります。
◆動詞文の場合でも①〜③の場合は次の理由から「は」が使われます。
まず、①ですが、「私」や「あなた」はそれが指しているものが常に了解されている要素です（そうでなければコミュニケーションはできません）。一方、主題はそれについて何かを述べるためのものですから、それが指しているものは明確でなければならず、そのため「私」や「あなた」は主題になりやすいのです。一方、②や③で「は」が使われるのはこうした場合は文が（形容詞文や名詞文と同じく）状態的（属性づけ的）になるためです。
◆なお、規則２から通常「は」を使う場合に「が」を使うと総記の解釈になります（ただし、３の(3)のような形容詞を述語とする現象文や次に述べる否定語を述語とする現象文の場合を除く）。
３ (3) （高原でバスを降りた直後に）うーん、空気がうまい。
【もう少し】
◆上述のように、否定文の場合通常「は」が使われ、(6)のように「が」を使うとその「が」は総記と解釈されます。
(6) 田中さんがパーティーに来ませんでした。
しかし、あるものや出来事が存在しないことを「発見」した場合は次の(7)(8)のように「が」を使ってもその「が」は中立叙述的に解釈されます。
(7) あっ、財布がない。
(8) あっ、かぎがかかっていない。
これらは現象文ですが、こうした文が使われるのは話し手が反対の予測を持っていたときに限られます。例えば(8)は話し手が「かぎはかかっている」と思ってノブを回したのにかぎがかかっていなかったという場合に使われます。