According to the Catholic Church, is there any supernatural (non-physical, non-mathematical, non-scientific) part of a human being?

Breaking down the question first, bear with me.

My previous understanding of the Catholic Church's teaching was that a human being is of two conjoined natures: physical and spiritual.

Glad this was your previous understand because a human being hasa human nature. Possibly you're thinking of Jesus who has two natures, human and divine See Hypostatic Union. St. Thomas Aquinas givs a good historical account of the meanings of the word nature which you can read in On Being and Essence. I found it in The Pocket Aquinas, he says Aristotle says "every substance is a nature" and Boethius says "every being which the intellect can in any way grasp is a nature"

And Augustine says this:

And if you happened to suppose, before receiving the instruction from this teacher, which you are rejoicing to have received, that the human soul is a portion of God's nature, then you were ignorant how false and terribly dangerous this opinion was. And if you only were taught by this person that the soul is not a portion of God, then I bid you thank God as earnestly as you can that you were not taken away out of the body before learning so important a lesson. For you would have quitted life a great heretic and a terrible blasphemer. However, I never could have believed this of you, that a man who is both a catholic and a presbyter of no contemptible position like yourself, could by any means have thought that the soul's nature is a portion of God. I therefore cannot help expressing to your beloved self my fears that this man has by some means or other taught you that which is decidedly opposed to the faith which you were holding.

Which I think is awesome.

Also, my previous reasoning was that things like consciousness, the ability to feel and especially free will are impossible in the natural/physical/mathematical world, where all that is possible are non-conscious, non-free, more or less sophisticated mechanisms.

E.F. Schumacher, in A Guide of The Perplexed synthesized Catholic teaching into 4 fields of being (Matter, Life, Consciousness and Self-Awareness). Wherein you had possibly combined the top two. He says lower animals and humans each posses consciousness and the ability to choose according to instinct, but only at the top level of being, where you are self-aware are you able to utilize those lower levels of being. So humans can use free will to seek the good (which is why God gave you free will). and "He finds his perfection "in seeking and loving what is true and good.'" ccc 1704

Therefore, I would say, free will must have supernatural origins and the claim that a human being has free will implies that there must be a supernaturnatural, spiritual, non-mathematical, non-physical, non-scientific part of the human nature, that cannot be researched nor explained by scientific means.

However, now I am being told that what I was thinking and saying were all heresies. I am being told that according to the teaching of the Catholic Church there is no supernatural or spiritual part nor dimension in the human being or human soul.

It is because you used the word "part" which makes Catholics nervous. Whenever you start breaking down human nature to its constituent parts you start to have them battle and you either wind up repeating the Manichean heresy where the spiritual was good and the physical was bad or you repeat the Arian heresy where because Jesus was just a really great guy, the physical nature was super important and the spiritual unattainable and forgettable.

The only fundamental difference between humans and animals, according to the Church, is that God has gifted humans with His grace to a greater extend than animals, and because of this God's favor humans are granted immortality - but otherwise, humans are really simply more intelligent animals and nothing more.

if "Granted immortality" is a comic book way of saying, they are given an immortal soul, then yes.

Therefore free will, if existent, is absolutely within the scope of science and probably will be fully explained by science.

I believe St. Thomas would agree that this is scientifically explicable.

Man has free-will: otherwise counsels, exhortations, commands, prohibitions, rewards, and punishments would be in vain. In order to make this evident, we must observe that some things act without judgment; as a stone moves downwards; and in like manner all things which lack knowledge. And some act from judgment, but not a free judgment; as brute animals. For the sheep, seeing the wolf, judges it a thing to be shunned, from a natural and not a free judgment, because it judges, not from reason, but from natural instinct. And the same thing is to be said of any judgment of brute animals. But man acts from judgment, because by his apprehensive power he judges that something should be avoided or sought. But because this judgment, in the case of some particular act, is not from a natural instinct, but from some act of comparison in the reason, therefore he acts from free judgment and retains the power of being inclined to various things. For reason in contingent matters may follow opposite courses, as we see in dialectic syllogisms and rhetorical arguments. Now particular operations are contingent, and therefore in such matters the judgment of reason may follow opposite courses, and is not determinate to one. And forasmuch as man is rational is it necessary that man have a free-will.

But, in conjunction with the Catechism passage I referenced above (ccc 1704) man's free will is placed in him by God so that he can choose to be good. I believe that's the only satisfactory answer to why does God give us free will if we can abuse it so badly.

Some people I was talking to were telling me that was I was believing were non-Christian views of Plato, and that I was guilty of believing and spreading the "heresy of Platonic dualism", since the Church has rejected the views of Plato and instead adopted the views of Aristotle, as described above, through St. Thomas. Other people were telling me that while my views were not yet heretical, because these views, since adopted by St. Augustine (who had been inspired by Plato), did have their place in the Church, nevertheless they were unfavorable, since the majority of theologians were instead holding the views of St. Thomas, who had been inspired by Aristotle.

St. Augustine rejected the Manicheanism with the help of the neo-platonists. Comparing the philosophical truths against the the "Fables of Mani" allowed him to reject Manichaenism and eventually seek truth in the Catholic Church. St. Thomas certainly referred to Aristotle a lot in his works and I know much is made of the dichotomy, but I think "modern philosophers" like G.K. Chesterton and St. John Paul II were more apt to pull the truths out of both Aristotle and Plato; there are problems with both philosophers.

The view that free will is a purely natural phenomenon that does not and can not have supernatural origins, since there is no such part nor dimension in the human being is, I have to admit, absolutely counter-intuitive for me and is absolutely opposite to how I used to understand the teaching of the Church.

If free will had no supernatural origins, then I think you'd admit it had to be passed down from parents to child. This is good because passing down supernatural gifts from parents to child is another heresy called Traducianism. But, if you read Martino Wong's excellent succinct answer you'd read that the soul is created by God at conception.

Given St. Thomas's definition of free will, it can only by held by rational animals. If you can conceive of a rational animal without an immortal soul, then you can conceive of a being with free will and no supernatural involvement in the creation of that soul. This was Frankenstein's monster's problem.

Now to answer the question.

No, there is no dimensionality in the soul - dimensionality being a mathematical construct useful to understand Newtonian physics. E.F. Schumacher persuasively argues that there are levels of being involved where-in the top level (us) has all the powers of being, life, consciousness, and self-awareness that we need to master the lower orders. I can see how it might be useful to think of these as dimensions though - maybe they are? In Edwin Abbot's Flatland (which is not devoid of religious symbolism), it was clear you could only describe a lower order dimension from the higher order dimension. And that's the same for E.F. Schumacher's levels of being. But there is no dimensionality in a brick, it is not at times a 2-d brick, even if that's all a piece of paper can conceive it to be. Likewise, there is no dimensionality in an immortal soul. Your cat has no idea what is going to happen to you after you die.

On the other hand, there is a "spiritual life" which we need to cultivate, but it's not divorced from material life - and we know that because God will resurrect our bodies at the end of time. There are two heresies which butt heads: Rationalism and Fideism. One needs to approach Faith and Life with body and soul.

Yes, it is perfectly rational to study free will from an anthropological and evolutionary standpoint. It should, however, point you to the fact that God had a pretty good idea what He was doing when He made us. Maybe scientists find free will written in our DNA and can turn it off with gene therapy, that won't be a whole lot different than a person whose brain has effectively left them without a semblance of free will. It would be a disordered state for a human to be in. And in the end, all that disorder will be fixed by the Resurrection.

Free will, not exactly as you know it, ought to exist in Heaven. Our Lady had free will, she was able to follow her intellect perfectly and do what was right completely by a singular grace to be free from original sin. We hopefully will share that grace in Heaven. There, free will will be properly understood as the Catechism defines it as the freedom to do what is right.

The answer can be found here in the Catechism of the Catholic Church; in particular, it says:

366 The Church teaches that every spiritual soul is created immediately by God - it is not "produced" by the parents - and also that it is immortal: it does not perish when it separates from the body at death, and it will be reunited with the body at the final Resurrection.

This paragraph makes pretty clear that the Catholic Church says there is a part of each human that is not “tangible” or “mathematical”.

The other paragraphs in this sections explain it a little better and I think can provide an answer to your other doubts.