SLM provided an excellent review from Irenaeus to Nicea (see here), so I will focus on the earlier end of the spectrum, from the Apostolic Fathers to Irenaeus (I'll include Irenaeus too though because, with the possible exception of the Shepherd of Hermas, Irenaeus addressed the OP's questions more directly than any other early Patristic writer)
Lake of fire = Gehenna
It is argued in the OP & in other posts that the "lake of fire" in Revelation refers to the same thing as "Gehenna" in the Gospels. A side-by-side comparison of the passages shows this is a very straightforward interpretation.
Lest we have any doubt, however, Irenaeus of Lyons makes the equivalence explicit:
Moreover," he says, "the book of life was opened, and the dead were
judged out of those things that were written in the books, according
to their works; and death and hell were sent into the lake of
fire, the second death." Now this is what is called Gehenna,
which the Lord styled eternal fire (Against Heresies 5.35.2)
The errors are at the extremes
The early Patristic writings do not contain some of the more extreme notions of hellfire that are found in the 4th-century, such as:
- Arnobius of Sicca--the earliest expositor of what is clearly annihilationism (source). Arnobius was harshly rejected by his contemporaries
- Lactantius--preacher of the cartoonish view of hell often depicted in later artwork (seriously, imagine what hell looks like in a cartoon, that's a pretty good take on the ghastly portrayal given by Lactantius)
Eternal conscious separation
I've discussed the Biblical basis for death as separation elsewhere; this view was explicitly taught by Irenaeus:
And to as many as continue in their love towards God, does He grant communion with Him. But communion with God is life and
light, and the enjoyment of all the benefits which He has in store.
But on as many as, according to their own choice, depart from God. He
inflicts that separation from Himself which they have chosen of their
own accord. But separation from God is death, and separation from
light is darkness; and separation from God consists in the loss of all
the benefits which He has in store. Those, therefore, who cast away by
apostasy these forementioned things, being in fact destitute of all
good, do experience every kind of punishment. God, however, does not
punish them immediately of Himself, but that punishment falls upon
them because they are destitute of all that is good. Now, good
things are eternal and without end with God, and therefore the loss of
these is also eternal and never-ending. It is in this matter just as
occurs in the case of a flood of light: those who have blinded
themselves, or have been blinded by others, are for ever deprived of
the enjoyment of light (Against Heresies 5.27.2)
He that believeth in Me is not condemned," that is, is not separated from God, for he is united to God through faith. On the
other hand, He says, "He that believeth not is condemned already,
because he has not believed in the name of the only-begotten Son of
God; "that is, he separated himself from God of his own accord (ibid)
The Shepherd of Hermas repeatedly refers to punishment/death/destruction as being cast out and separated/barred from the tower (heaven). In Vision 3 he spoke of the stones (people) that were cast away from the tower:
5 "But those whom they rejected and threw away, who are they?"
"These have sinned, and desire to repent, therefore they were not cast
to a great distance from the tower, because they will be useful for
the building, if they repent. They then that shall repent, if they
repent, will be strong in the faith, if they repent now while the
tower is building. But if the building shall be finished, they have no
more any place, but shall be castaways. This privilege only they
have, that they lie near the tower.
1 But wouldst thou know about them that are broken in pieces, and
cast away far from the tower? These are the sons of lawlessness. They received the faith in hypocrisy, and no wickedness was absent
from them. Therefore they have not salvation, for they are not useful
for building by reason of their wickednesses. Therefore they were
broken up and thrown far away by reason of the wrath of the Lord,
for they excited Him to wrath. (Vision 3, 5:5-6:1)
Lest we conclude that being broken up refers to annihilation, later in the same work Hermas parallels dying eternally with being cast out of the tower (heaven):
2 If then he that ought to do good committeth wickedness, does he not
seem to do greater wickedness than the man that knoweth not God?
Therefore they that have not known God, and commit wickedness, are
condemned to death; but they that have known God and seen His mighty
works, and yet commit wickedness, shall receive a double punishment,
and shall die eternally. In this way therefore shall the Church of God
3 And as thou sawest the stones removed from the tower and delivered
over to the evil spirits, they too shall be cast out; ...Thus
shall it be with the Church of God also, after she hath been purified,
and the wicked and hypocrites and blasphemers and double-minded and
they that commit various kinds of wickedness have been cast out.
(Similitude 9 18:2-3)
In chapter 22 of the same Similitude those who repent not are said to have an abode with the devils/tempters, suggesting they have been separated, but still exist; chapter 33 parallels living in eternity with living unto God, suggesting the absence of life means existence without God.
The same author spoke of death in terms of being turned away from God with no way of return:
I say to him, "Sir, I comprehend not what means "unto death," and what
"unto corruption". "Listen," saith he; "the sheep which thou sawest
gladsome and skipping about, these are they who have been turned
asunder from God utterly, and have delivered themselves over to the
lusts of this world. In these, therefore, there is not repentance
unto life. For the Name of God is being blasphemed through them. The
life of such persons is death. (Similitude 6 2:3)
The final clause indicates that death (or destruction) is not annihilation. See also Vision 1 1:8, which pairs death with captivity.
Similitude 8 of the same work relates life to being admitted into the tower (heaven), and death to being prohibited from entering the tower: "they lost their life" appears to be equivalent to losing their place in the tower.
There are exceedingly many Patristic quotes regarding eternal fire that are taken directly out of Matthew or Revelation. Most provide no more detail on the nature of the fire/torment/punishment/destruction than does the New Testament. Some of the earliest sources state quite baldly that sin leads to death, without defining what that death is (e.g. Barnabas, the Didache)
Often, however, the focus is on the unending nature of the fire itself:
And they found the fire of their inhuman torturers cold: for they set
before their eyes the escape from the eternal fire which is never
quenched (Martyrdom of Polycarp 2:3)
Such an one becoming defiled [in this way], shall go away into
everlasting fire (Igantius, Epistle to the Ephesians, ch. 16)
they are punished with grievous torments in unquenchable fire (2
Clement 17:7--note that although this epistle is early & attributed to Clement, we don't actually know who wrote it)
shall send those of the wicked...into everlasting fire (Justin,
First Apology ch. 52)
When the Patristics speak of what will happen to the wicked, it is not unusual for them to refer to eternal punishment rather than eternal torment. Such statements allow ambiguity as to whether the punishment has eternal consequences or an infinite duration:
Thou threatenest that fire which burneth for a season and after a
little while is quenched: for thou art ignorant of the fire of the
future judgment and eternal punishment (Martyrdom of Polycarp 11:2).
For among us the prince of the wicked spirits is called the serpent,
and Satan, and the devil, as you can learn by looking into our
writings. And that he would be sent into the fire with his host, and
the men who follow him, and would be punished for an endless duration
(Justin, First Apology ch. 28)
1 Clement, notably, mentions both, but no timeframe:
He forsaketh not them which set their hope on Him, but appointeth unto
punishment and torment them which swerve aside (1 Clement 11:1)
The Shepherd of Hermas mentions both as well:
they so suffer who are punished and tormented (Similitude 6 5:6)
The Epistle to Diognetus appears to cover all the bases, just to be sure:
thou shalt despise the apparent death which is here on earth, when
thou shalt fear the real death, which is reserved for those that shall
be condemned to the eternal fire that shall punish those delivered
over to it unto the end (Diognetus 10:7)
The Shepherd of Hermas explicitly speaks of punishment that is temporary (this can be read as a description of Hades rather than Gehenna):
Yet they shall be fitted into another place much more humble, but
not until they have undergone torments, and have fulfilled the days of their sins. And they shall be changed for this reason, because
they participated in the Righteous Word; and then shall it befall them
to be relieved from their torments (Vision 3 7:6)
the time of the punishment and torment is long (Similitude 6 3:4)
(Note that Similitude 6--if read in full--is consistent with the view that many will receive a severe but temporary punishment in Hades, whereas a subset will receive the second death in Gehenna)
Justin, ever the ambiguous philosopher, also provides some of the most explicit statements regarding unending punishment:
some are sent to be punished unceasingly into judgment and
condemnation of fire (Dialogue with Trypho ch. 45)
He shall raise all men from the dead, and appoint some to be
incorruptible, immortal, and free from sorrow in the everlasting and
imperishable kingdom; but shall send others away to the everlasting
punishment of fire (Dialogue with Trypho ch. 107)
we know from Isaiah that the members of those who have transgressed
shall be consumed by the worm and unquenchable fire, remaining
immortal (Dialogue with Trypho ch. 130)
Justin has sometimes been called a proponent of annihilationism; I suggest that he forecloses that possibility in his First Apology:
shall send those of the wicked, endued with eternal sensibility,
into everlasting fire (Justin, First Apology ch. 52)
Punishment by degrees
A number of the early writers acknowledge punishment for the wicked, but not equal punishment for all. Rather, punishment was thought of in gradations, depending on the severity of the wickedness.
God, even Him who has prepared eternal fire for every kind of apostasy
(Against Heresies 5.26.2)
The Shepherd of Hermas indicates that punishment is proportional to the wrong-doing:
1 I say unto him; "Sir, declare unto me this further matter...they
that live in self-indulgence and are deceived undergo torments during
the same length of time as they live in self-indulgence and are
deceived." He saith to me, "They undergo torments for the same length
of time. (Similitude 6 3:1)
This concept of punishment and greater punishment is also discussed by Hermas in the passage from Similitude 9 quoted earlier in this post; see also a more extended treatment by the same author in Vision 3 7:1-6.
The idea of gradations in blessings/punishments is also found in the later writings of Origen.
Was Origen a Heretic?
It is true that Origen was called a heretic, but context matters. Unlike some of the most notorious heretics (e.g. Marcion, Valentinus, Tatian, Arius), who were thoroughly and unmistakably denounced by their contemporaries, Origen was not declared a heretic by his contemporaries, he was considered the greatest scholar of his era.
Origen was declared a heretic almost 3 centuries after his death, because his views fell on the wrong side of a theologically-political (or politically-theological, if you like) debate. To use the modern parlance, Origen was "cancelled" for holding antiquated views that were not socially acceptable 300 years later.
Furthermore, the declaration that Origen was a heretic was made by...wait for it...Emperor Justinian I. It was only after the despotic emperor came down on Origen's teachings that some clergy anathematized some of Origen's teachings (source). Justinian had a way of getting people to say what he wanted them to say...or else.
(Pro-tip for surviving if you ever find yourself in the 6th century Byzantine Empire: if you disagree with Justinian, it's probably best to keep it to yourself)
All that to say not that Origen is inerrant (far from it), but that Origen's writings occupy a very significant place in Patristic authority. If we want to know what the church believed or what it was debating in the early 3rd century, ask Origen.
Did the Early Church believe in Annihilationism?
I see no clear evidence of annihilationism in Christianity prior to the 4th century.
Did the Early Church believe in eternal conscious torment?
Belief in conscious torment/punishment is ubiquitous. The timing/duration of that torment/punishment is not so unanimous. Justin emerges as one of the strongest voices for endless torment. Others suggest gradations in punishment and/or a non-infinite interval of torment.
Did the Early Church believe in eternal conscious separation?
Irenaeus taught this explicitly; the Shepherd of Hermas is heavy on the metaphors, but appears to support this as well.
There are many points of divergence in the views of the early church--I suggest that the matters relevant to the OP on which there is broad agreement are:
- The lake of fire = Gehenna = second death
- The fire is eternal
- There will be conscious punishment for those who do not repent
- Cessation of existence appears to be a foreign concept to these writers