This seems to happen for no other reason than it sounds more natural for native speakers for no specific, definable reason.
As Fernando correctly pointed out, it's not the gender that varies. In Portuguese, all nouns have a gender. What happens is that the definite article can be omitted in some cases.
The names by which speakers of a language call stuff whose proper name is in another language (for example, country, city names, etc) are called exonyms (exônimos).
The genders of exonyms follow basically the same general gender rules as any other noun. For example, most words ending in -a are feminine, and so is Alemanha. Both civil and perfil are masculine, and so is Brasil. Hospital, local and natal are masculine, and so is Portugal.
The question remains, though: why do we omit the definite article for words seemingly so similar? (e.g. *Passarei o natal em Portugal).
But there seems to be no definite answer to that. Here is a statement from Prof. Sérgio Nogueira, a well-known teacher of the Portuguese language:
A maioria dos nomes de países exigem o artigo: a Argentina, o Brasil, a Alemanha, o Peru, a Espanha, o Uruguai... Mas há um bom número que rejeita o artigo: Israel, Portugal, Cuba, Angola, Moçambique, Cabo Verde...
Source: G1 - Quais cidades, estados brasileiros e países pedem artigo definido?
And he concludes, not only on the matter of articles for countries, but also for cities and states:
Como podemos constatar, não há propriamente uma regra.
Here is a map from Wikimedia on the genders of articles in Portuguese. Green is masculine, Purple is feminine, yellow means article is omitted.
For non-native Portuguese speakers, I'm afraid the only way out is memorisation, and a developed sense of what sounds right over time. All evidence from my research points to the fact that if there is a rule, it's complex and/or obscure enough not to be taught as one.
PS: After some research, and despite Fernando's answer, I decided to try my own answer.