Are the following sentences valid:
It didn't used to happen.
It didn't used to have been there.
And if so, what tenses are they?
"Didn't used to ..." is a colloquialism (i.e. informal) combining "didn't" and "used to" and both are past tense, like a double negative. And like a double negative, it's not wrong, just not formal. In fact both forms are common and informal.
It is used quite often by many people, including journalists:
By the way, although Google NGrams can be misused, I think a direct comparison here using that tool is informative here.
It shows that both terms are used and that "didn't used to" has gained ascendancy over the latter half of the 20th century.
It should be "use", because "did" already makes it past tense, so "-d" is not needed.
"didn't use" is simple past, and "to have been" is an infinitive with the verb a past perfect.
This graph shows that only recently has "didn't used to" rise in use. This is also characterized with the rise of usage and popularity with many informal and actually incorrect English.