You will certainly end up officially binary at some point, and you might not get to choose.
As of 2023, the Czech legal system is strictly binary and does not even leave any room for self-identification of gender. The official sex/gender is assigned at birth, and the only way to have it legally changed is to undergo reassignment surgery. Loads of official forms of all sorts ask for gender and present just two options, so there's little room to accommodate officially non-binary foreigners like you. Working in Czechia absolutely requires submitting at least some of those forms (health insurance application, tax return, etc.).
The Czech Public Defender of Rights has quite extensively analysed a case of a non-binary person in 2015 as case 206/2012/DIS (official English version as PDF), which I'll use as my main reference here. AFAIK, nothing of any substance has changed in the law since then.)
Quoting from the English version:
In terms of the law, sex/gender change of an individual takes place by means of a sex reassignment surgery with simultaneous sterilisation and transformation of the genitalia. The New Civil Code thus associates gender with the physical sex, irrespective of the psychological dimensions of gender and the internally experienced identity of a person.
and (emphasis mine)
The previous subchapters dealt with the issue of sex/gender change in the current bipolar gender system used in population records, which distinguishes only two genders: the male and the female. A solution consisting in a change of the administrative sex/gender to female is, however, less preferable to the Complainant than being recognised as a being of “neutral gender”. Such a variant is not permissible under the current legislation; introducing a third gender category, i.e. neutral, is exclusively a matter of the legislator’s choice.
Now, I am fairly certain that having Other gender in your documents is not a legally valid reason to refuse a work permit, so it should not be entirely impossible to get one in your situation.
However, at some point, you will simply be recorded as Male or Female and then have to live with the choice ever since. And given that Czech law does not allow self-identification of preferred gender, it might be that you will not get to choose but will have to produce a document (such as a birth certificate) saying you're either Male or Female. (Here I'm purely speculating since I have no idea how people with a passport saying "O" are handled. But you can certainly expect a lot of confusion.)
You can also certainly expect a whole lot of uncomfortable situations when somebody notices your passport says "Other".