Studiował malarstwo w warszawskiej ASP (1948-54) pod kierunkiem Artura Nachta-Samborskiego. Zadebiutował w okresie poprzedzającym "odwilż", podczas Ogólnopolskiej Wystawy Młodej Plastyki Przeciw wojnie, przeciw faszyzmowi w warszawskim Arsenale (1955). Oryginalność jego osobistej, nasyconej egzystencjalnymi lękami formuły malarstwa figuratywnego, docenili krytycy francuscy, którzy w roku 1959 przyznali Lebensteinowi Grand Prix na I Międzynarodowym Biennale Młodych w Paryżu. Od tego momentu malarz mieszkał we Francji, a ostatecznie po wielu latach, w 1971 roku, przyjął francuskie obywatelstwo. Związany był ze środowiskiem paryskiej "Kultury", ilustrował wydawane tam opowiadania G. Herlinga-Grudzińskiego. Ilustrował Folwark zwierzęcy G. Orwella wydany przez Instytut Literacki, zaprojektował witraż ze scenami z Apokalipsy w kaplicy Pallotynów w Paryżu. W 1976 roku otrzymał Nagrodę Fundacji im. A. Jurzykowskiego z Nowego Jorku. W 1987 roku otrzymał niezależną Nagrodę im. J. Cybisa.