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.
8時になったら電気が消える。[one-time change / neutral]
8時になったら電気は消える。[one-time change / contrastive]
Now, let’s look at the following.
8時になっても電気が消えない。[one-time change / unexpected]
8時になっても電気は消えない。[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.