Greg Egan's _Diaspora_ (1997) and _Oceanic_ (1998) come to my mind. Of course not really predating, with what we now recognize as gender fluidity existing for thousands of years, but in any case early texts long before the notion rose to be widely known in our culture.