Belenko has stated in his book, in numerous publications and in LIVE appearances prior to his death that the MiG-25 in his squadron had NO ejection seats. This has been confirmed by other former Soviet MiG-25s drivers who have either immigrated or defected to the west. It seems however in later years (Post 1976) the MiG-25 did receive a seat.
As far as I know Belenko was the only MiG-25 pilot who defected to the west . In fact, before 1989 he was the only pilot of the soviet Air Force and PVO who has defected.
Back to the question:
I have 3 different books with the description of the construction of the Foxbat, unfortunately all in russian. They all confirm the presence of an ejection seat even in the prototype plane and in the earliest versions ,both fighter and recce - MiG-25P and MiG-25R respectevly.
So according to the information in these books there was an ejection seat KM-1 installed on the first versions of the MiG-25R (1967),which was changed later to the more advanced KM-1M. MiG-25P was equipped with this seat as well (V. Iljin, M.Levin, Sovremennaja Aviacija,M.,1992).
The only changes were made after Belenko's defecton was the completely changed "friend-foe" system which became useless after his betrayal - that costed about 2 billion soviet rubles - the development of the first soviet aircraft carrier was cancelled due to this reason, than a better radar was installed and some other changes in avionics were made.
And quite frankly, can you imagine a mach 3 plane without an ejection seat? I highly doubt any pilot would climb in that airplane even to make a touch-n-go training flight - the Soviet Union was not known for a very human treatment of its own citizens,but we shouldn't exaggerate THAT much.
As for Belenko, I don't know why he lied all the time on that issue -he could have his reasons for this. BTW, are you sure he's dead by now? There're some rumours in Russia now and then , that he was killed in a plane accident 2 or 3 years ago , but then, I saw an interview with him dated 2005 or something like this.