I’d use the native WordPress custom menus mostly because they allow the admin to edit the content easily. I don’t see the other solutions you propose as flexible enough for a client to use. I don’t think it’s possible to avoid complexity completely in this case. Better to focus on educating the client.
By the way, though, you missed out the possible problem that WordPress custom menus don’t replicate the actually structure of the site, so the client has to reproduce this when they add items to the menu.
