Is my understanding correct?
These are not cleft sentences. While they both contain a form of to be, it is not referring to phrase or similar. You can easily get rid of to be without changing the grammar:
The quality of air remains at its lowest since 1990.
Yesterday constituted their first free concert since 2003.
Somewhat analogous cleft sentences would be:
It’s since 1990 that the quality of air hasn’t been so low.
2003 was when the band last gave a free concert.
Note that Yesterday can be regarded as a reduction of Yesterday’s event.
[…] how could we justify this usage of since with a tense other than the present perfect?
Since [time] usually demands the present perfect when it is used as a sentence adverb, i.e., when it pertains to the entire remaining sentence, e.g.:
The quality of air has been low since 1990.
However, in your examples since is not a sentence adverb but modifies adjectives or nominalised adjectives, namely its lowest and first. If since applied to the entire sentence in your first example, the quality of air would have constantly been at the same, record-low value since 1990. If you change the tense to present perfect, you get a sentence that can be interpreted this way:
The quality of air has been at its lowest since 1990.
In your second example, if since applied to the entire sentence, yesterday and the concert would have lasted since 2003 (which is as nonsensical as it sounds), and the concert would be the first free concert at all.