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). W roku 1956 artysta związał się z niezależnym Teatrem na Tarczyńskiej, prowadzonym we własnym warszawskim mieszkaniu przez Mirona Białoszewskiego. Lebenstein miał na Tarczyńskiej pierwszą wystawę indywidualną. Tworzył w tym czasie figury kreślone, następnie figury hieratyczne i wreszcie figury osiowe. Były to kompozycje (rysunkowe i malarskie) z umieszczonymi centralnie, wertykalnymi sylwetami skrajnie uproszczonych (w wersji rysunkowej niekiedy przypominających owadzie stwory) postaci ludzkich, najczęściej kobiecych. Oryginalność tej 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.