In its context προ in Colossians is easily interpreted as "before" in rank, not in time. BDAG gives "rank" as a possible meaning for προ, although it classifies this instance under time. For some reason or another most "literal" translations have "is" here, so at least they have not seen it necessary to interpret it as an imperfect "was" or "existed". If the grammar would be clearly normal, i.e. the translators who often have read much Greek would have instinctively understood it as "was", they would probably have translated it so. But I understand this isn't clear cut because many translations interpret it as "existed".
The style of the Col passage feels philosophical, and in my experience that kind of style often leads to using language and grammar more freely (even making it bear burdens it wouldn't bear in more mundane prose). I don't have difficulties to understand Paul meaning both temporal and qualitative precedence here, so it doesn't have to follow strict grammatical rules.
John 8:58 is of course (in)famous because of the theological consequences, and it's difficult to discuss it without wider exegesis and theology. My theology doesn't depend on this so I'm open to hearing actual explanations for how the present tense can here mean the same as imperfect in Koine or perfect in English would mean. As has been argued in some commentaries, if John would have meant just that Jesus existed, why not say so by using the imperfect? And why would the opponents go mad only after this saying, not before it when they mocked Jesus for already implying he existed before Abraham? In the context the present tense and the whole saying is outstanding and the phrase is the closest which could have been used in Greek to make connection to existence of God clear. The problem is made more complex when we remember that they probably spoke Aramaic and what John writes is an approximation, using possibilities (or impossibilities!) of Koine instead of Aramaic.
In any case the biggest problem for me to accept "I was" or "have been" here is not theological, but that nobody has actually proved it. So gimme parallels.
BTW, as you can see, I don't say "I AM" here is directly the name of YHWH. If there's a connection it's more complicated.