Для пересечения границы другого государства вам нужно не гражданство какой то страны, а travel document. В России это загран паспорт, паспорт моряка или дипломатический паспорт. Возможно получение удостоверение беженца или даже справки о потере паспорта. Если у вас вообще ничего нет, идете в ближайшее отделение милиции/полиции и просите выдать вам справку об утере. С ней вас точно выпустят из страны, и скорее всего даже впустят в другую, особенно если правильно все подготовить.
У нас в России они считаются лицами без гражданства, сокращенно ЛБГ. Визу в Россию для ЛБГ сделать можно, но они идут по категории миграционно опасные страны.
Я знаю человека, у которого нет гражданства, но имеется вид на жительство в Германии (розовая такая карточка). С видом на жительство и какой-то справкой о том, что он апатрид он может путешествовать по Шенгену.