coexist is not the same meaning as together. Agreed with Troy.
I would not say it's redundant. B/c for example, 2 countries can "coexist" in the same world (like CAN & USA), but that doesn't mean they're "together".
Bob says: "We can coexist on this island together!"
Red replies: "No, we just need to coexist; I don't want to see you on this island, ever"