I agree with Simon's advice. I find that the gains that you obtain from using any external method of imputation is often inferior to an internal method, and on top of this, exposes you to even more potential of severely screwing up with respect to data leakage.
That being said, besides using an algorithm that automatically handles missing data for you (which often are models based off trees/rules, though they do not all use the same method of imputation), there are external based methods that might be of interest. I find that as you get more "fancier" the results are not enough of an improvement compared to the computational pain it is to use them. Starting with the simplest;
1) Mode imputation; simply use the most common gender in your training data set. For your test dataset, use the most common gender that exists in your training data set. Since there are 5x more males than females, this would result in you almost certainly assigning male to all observations with missing gender. Obviously, this doesn't use a whole lot of information besides the observed frequency of the class, but this method is pretty common and often "good enough".
2) kNN imputation; take the k most closest neighbours (that do not have missing genders) to the observation that you wish to impute gender for. Then, simply treat each of these k neighbours as a committee of "voters" who use their own gender as their vote. Weight each vote by how close they are (based off other variables that aren't missing) to the observation with the missing gender value. Whichever gender wins in votes gives you the imputed gender.
This method to me, is a clear improvement over method 1) and is also quite fast. However, this will require you to center and scale your data (because we are using distances to define "closeness") and k is now a tuning parameter which further complicates matters.
3) Random Forest imputation; initially, use method 1) to temporarily fill in your missing genders (just mode impute). Then, run a random forest algorithm on the imputed dataset, generating N trees. Compute what is referred to as the "proximity matrix", where each $(i,j), i \ne j $ entry in this matrix (diagonal entries are all 0) is equal to the number of times observations $i$ and $j$ fall in the same terminal node through the entire forest divided by the number of trees in the forest. Using these proximities as weights, calculate a weighted vote of all the observations that do not have missing genders using their genders as their "vote". Change any prior "temporary" imputed genders from the initial mode imputation to what has been calculated by the random forest if they differ. Repeat (fit another random forest again), using the imputed genders from the previous random forest, until all observations converge to a single gender or until some stopping criteria.
This method is incredibly costly but is probably pretty accurate (I haven't used it much because it is slow). You will also have to deal with an additional tuning parameter; namely how many variables you wish to randomly select in each split.
4) MICE: I haven't really studied this method too closely, but you seem to have mentioned it. One thing I will say is that all of these methods can be used with any kinds of missing data; categorical (like gender) or continuous (like birth_date, though for method 1) you would probably use mean/median imputation instead for continuous variables, and for methods 2 and 3) you would no longer use a "vote" but a weighted average). Ultimately, MICE is just one of many methods of imputation that you can use which is why one needs to properly validate their modelling choices within cross validation if you choose to use an external method of imputation. If you have the time, try a bunch of methods and use the highest performing one. Otherwise, use a method that seems "reasonable enough" given time constraints.
