As Christine said it in the commentary, I would recommend to read a lot in French.
Except for a small number of words*, gender is intuitive for every native speaker (except maybe the younger ones). Because they've always heard the words with the right gender when their parents or teachers speak when they were young.
Using Chritine's words, you can't think about genders when you speak, or it will take you five minutes per sentence. You just know. But obviously, given the number of words, students can't learn all genders one by one (like French children do when they have to learn English irregular verbs).
Reading French, the students will slowly and unconsciously get used to the gender of words. So when they speak, the right one will come naturally in mind. At the beginnning, they will be wrong sometimes. But it wil come.
* There are some words, like "après-midi", which gender is not clear even for native French speakers. In the case of "après-midi", the dictionnary now allows both genders, because too many people were using the wrong one.