Lord Shiva, not to be confused with Rudra, who is an Amsa of Shiva, is called ,

Anaadi, without a Beginning,

Ayonija, one who does not stay in the womb.

He, as an Avatar,appears from nowhere and disappears in a flash, unlike Vishnu, who in His avatars was born of a human being.

Some of my researches show that Lord Shiva lived as a Human being before being elevated into Godhood, but this needs additional proof( I am working on it)

One also finds that Parvati, Shiva’s wife is called,

Poorvaja, beyond beginning, elder to the beginning, Poorva Plus Aja.

Aadya. the Beginning.

Lord Vishnu is described as

Anaadi,

‘Anaadi nidhano dhatha, vidhaatha dhathuruthamaha  -Vishnu Sahasranama.

What do the Vedas say?

Despite the Polytheism of the Vedas, the core message is that the Reality is

without Attributes,

without name and Form and is a

Principle.

The Upanishads spend the whole text on this point.

However, as Hinduism is aware of the fact that it is difficult for the mind to concentrate on a Vacuum, allows the worship of personal Gods as a tool for Self Realization.(Iswara)

Patanjali speaks of this in his Yoga Sutras as Iswarapranidhaana.

Please read my post  Does God have Name and Form

Necessity of God in Yoga Sutra

However one finds one God being placed ona higher pedestal than the others in Hindu texts.

This is called Henotheism.

This is to instill a higher degree of faith to the deity one is inclined to worship.

So we find various gods being praised as being Superior to the others, while the Reality Brahman is without name and Form.

As to Shiva , when compared to other Deities he is more often described as The One who is without a Beginning.

Tamil calls Him as Piravaa Yaakaip Periyon,

The Eldest who is Never Born.

But as I said earlier each Purana Praises One God.

Many mistake the birth of Rudra to that of Shiva.

Excerpt fro Srimad Bhagavatham(SB)

SB 3.12.4: In the beginning, Brahma created four great sages named Sanaka, Sananda, Sanatana and Sanat-kumara. All of them were unwilling to adopt materialistic activities because they were highly elevated due to their semen’s flowing upwards.
SB 3.12.5: Brahma spoke to his sons after generating them. “My dear sons,” he said, “now generate progeny.” But due to their being attached to Vasudeva, the Supreme Personality of Godhead, they aimed at liberation, and therefore they expressed their unwillingness.
SB 3.12.6: On the refusal of the sons to obey the order of their father, there was much anger generated in the mind of Brahma, which he tried to control and not express.
SB 3.12.7: Although he tried to curb his anger, it came out from between his eyebrows, and a child mixed blue and red was immediately generated.
SB 3.12.8: After his birth he began to cry: O destiny maker, teacher of the universe, kindly designate my name and place.
SB 3.12.9: The all-powerful Brahma, who was born from the lotus flower, pacified the boy with gentle words, accepting his request, and said: Do not cry. I shall certainly do as you desire.
SB 3.12.10: Thereafter Brahma said: O chief of the demigods, you shall be called by the name Rudra by all people because you have so anxiously cried.
SB 3.12.11: My dear boy, I have already selected the following places for your residence: the heart, the senses, the air of life, the sky, the air, the fire, the water, the earth, the sun, the moon and austerity.
SB 3.12.12: Lord Brahma said: My dear boy Rudra, you have eleven other names: Manyu, Manu, Mahinasa, Mahan, Siva, Ritadhvaja, Ugrareta, Bhava, Kala, Vamadeva and Dhritavrata.
SB 3.12.13: O Rudra, you also have eleven wives, called the Rudranis, and they are as follows: Dhi, Dhriti, Rasala, Uma, Niyut, Sarpi, Ila, Ambika, Iravati, Svadha and Diksh.
SB 3.12.14: My dear boy, you may now accept all the names and places designated for you and your different wives, and since you are now one of the masters of the living entities, you may increase the population on a large scale.’

Now there is video that explains the birth of Shiva quoting a text which says that Shiva declared  that Brahma to be His father, Vishnu ,Grandfather and he ( Shiva) is his great Grand father.(Posted at the beginning of the Post)

While this makes an interesting read, there is no authentic source for this.