How can I add a contact WITHOUT choosing an account to sync with?
If there's an option "local phone account" or something similar, then choose that instead of any Gmail account.

I can see this when I select "More Fields" in the "Add new contact" screen. Marshmallow, OnePlus One.