Were most of his 95 theses something that was already discussed among some parts the Catholic clergy, or was he proposing something completely new?
Yes and no.
Luther’s 95 Theses argue that the Church should not sell indulgences, because indulgences have no actual value. The sale of indulgences was controversial within the Church, and had been for some time. But there is a world of difference between someone saying, “We should not sell indulgences because indulgence sellers use abusive practices,” and someone (i.e., Luther) saying, “We should not sell indulgences because the Pope has no authority to grant indulgences.”
As I have talked about previously, Luther’s argument against papal power was central to his opposition to indulgences. (Incidentally, the Protestant position that people did not need to be subject to the Pope in order to be saved, and the Catholic position that they did, was the primary reason why the churches could not be theologically reconciled). This argument was deemed heretical, and was the one that nearly got Luther killed.
Few within the Catholic Church had made this claim before Luther - the Pope is central to the Church, and denying his authority in certain theological matters goes against traditional teachings. Few, but not zero. A notable example was Jan Hus, a Czech theologian a century before Luther. Hus also denied the efficacy of indulgences (opposing the inherent idea of a papal indulgence, not just the methods by which they were sold), and was ultimately burned at the stake. John Wycliffe, an English theologian of the late 14th century, also argued against papal power and indulgences. You can check out his text “De Papa” here; how’s your Middle English? Here’s a relevant bit:
We bileuen on cristis lawe þat ȝif man synnede neuere so longe, & were neuere asoylid of pope ne of his prest vndir hym, ȝif he wolde forsake his synne & be contrit for formere synne & ende þis lif on þis maner, god wolde forȝyue hym his synne. We kunnen not telle hou longe þat god wolde punysshe hym in purgatorye, & þis is more grace of god þan þe pope telliþ in his lawe, for he wole nedis constreyne men to be asoylid of hym or hise, but þis durste noon apostle do. & þus it is no bileue, as it is no bileue þat þis or þis is very pope.
In Modern English it might go something like this (Medieval English scholars, please correct any errors in my translation!):
We believe in Christ’s law that if a man sinned never so long (?), and were never availed of the pope nor of his priests under him, if he would forsake his sin and be contrite for his former sins and end this life in this manner, God would forgive him his sin. We can not tell how long that God would punish him in purgatory, and this is more grace of God than the pope tells in his law, for he will needs constrain men to be availed of him or his, but this darest no apostle do, and thus it is no belief, as it is no belief that this one or that one is truly pope. (Note that this last line is probably a reference to the Western Schism, ongoing in Wycliffe’s day, during which two different men claimed to be Pope, splitting Europe over who was legitimate)
Wycliffe drew the ire of much of the Church hierarchy, but lived out his days in relative peace before dropping dead of a stroke while giving a sermon in his old age. He and his writings were condemned decades later during the controversy surrounding Hus; Wycliffe's body was exhumed and burned.
So outright denial that the Pope could forgive sins, or that one’s sins could only be forgiven if one was subject to the Pope, was rare. But simply pointing out that the Church was tacitly allowing abusive practices within its ranks was neither heretical nor particularly uncommon. The Church itself was well aware of it. No less than the Fourth Lateran Council of 1215 tried to restrain problems with the clergy, banning drunkenness, unchastity, visiting taverns, hunting, and many other activities, threatening such clergy with removal from office. Clergy were “forbidden to receive churches and tithes from the hands of laymen without the consent of the bishops.” The Council acknowledged that “through indiscreet and superfluous indulgences which some prelates of churches do not hesitate to grant, contempt is brought on the keys of the Church,” and limited the length of indulgences which could be granted in varying circumstances. This council was 300 years before Luther, so the issues he addressed had been around for some time.
Even Thomas Aquinas got involved, writing that, while indulgences were theologically sound, the priest ought not to abuse the practice: "The priest cannot decide in the tribunal of confession how much shall be remitted by means of the key of orders from the punishment due; it is God Who appoints the amount to be remitted… If, however, [the priest] remits punishment without sufficient reason, so that men are enticed to substitute mere nothings, as it were, for works of penance, he sins by granting such indulgences, although the indulgence is gained fully."
So all this is to say that the controversy over the sale of indulgences was nothing new in Luther's day. His position that the Pope had no ability to remit the punishment of sins was much less common, though not unheard of.