Как мне поступить, если я до мая 2017 не успею получить немецкий пасспорт / выйти из украинского гражданства?

Если успеете выйти, но не успеете получить немецкое, то сможете запросить себе паспорт для лиц без гражданства. С ним вроде можно ехать. Узнайте в АБХ. Либо после получения гражданства, но до получения паспорта, тоже можно получить временный документ, узнайте можно ли ехать с ним. Вообще, при хороших раскладах и взятых везде заранее терминах, должны успеть. В среднем укладываются в 10 месяцев. Читайте ветку, поймете как ускорить потом процедуру, после выхода. А имеенно, вам нужно будет звонить в АП и как долько будет указ, сразу звонить в АБХ и просить начать повторную проверку, потом когда нужно будет сдавать паспорт, ехать лично и сразу сдавать и забирать бумагу о сдаче паспорта и т.д. и т.п. брать везде термины заранее и всё будет быстрее.)

но если меня выпустят с украинского гражданства во время поездки, я окажусь вообще без гражданства, хотя и паспорт будет ещё на руках..... Тем более мой вид на жительство привязан к моему паспорту...

Когда уже будут поджимать сроки, сходите в АБХ, узнайте что вам делать, объясните ситуацию, может вам дадут какой-то документ.