What predictive model to use to impute Gender?
You can use one of the popular gradient boosting tree implementations such LightGBM and XGBoost as your predictive model. They can handle missing values during training and the results are often better than any imputation done in preprocessing.

The way they achieve this is by using the splitting of the decision trees they are built on. The missing values are ignored when finding the best split, then once it is found they are allocated to whichever side will minimize the loss function most.