Вы немного неверно понимаете свои возможности.
1. Вы и Ваша супруга должны исходить не только из того, что у вас двоих есть, но и из того, что вы ходите получить на конечном этапе (ПМЖ или гражданство без выхода (последнее тоже возможно));
2. Если Ваша супруга родилась в Украине, то когда она уехала из Украины и где она была прописана/зарегистрирована на 1991 год;
3. Статус заграничного украинца вообще ничего не дает. Эта тема обсуждалась достаточно активно на данном форуме. Вердикт один - если хотите жить за пределами Украины, но быть носителем украинской культуры и обычаев - статус нужен, если же хотите переехать в Украину и тут жить, то получение статуса пустая трата времени, сил и денег.
4. Вы и Ваша супруга имеете все основания и для ПМЖ и для гражданства. Но в одном случае времени, сил и нервов придется потратить чуть больше, а в другом (супруга) практически не потратите.