No, each option has creatures that cannot use it
There are creatures who can only advance by HD, and other creatures who can only advance by class level. Therefore, it is not true that all creatures can choose.
Player characters must “advance” by class level
Really, player characters don’t advance the way non-player characters do at all. Instead, they advance when they “gain a level” via XP, which is a different process.
Advancing a Level: When your character’s XP total reaches at least the minimum XP needed for a new character level (see Table 3–2), he or she “goes up a level.”
(Player’s Handbook, pg. 58)
Leveling up always starts with choosing a class—and a class must be chosen, a non-class racial hit die is not an option:
When your character attains a new level, make these changes.
- Choose Class: […]
(Player’s Handbook, pg. 58)
This is not optional, and there is not an alternative.1 Savage Species (and some other publications) provide “racial classes” or “template classes” to allow a player character to effectively “gain levels” in a powerful race or template, and levels in those classes may even involve racial hit dice or level adjustment, but they are first-and-foremost classes, which they must be in order to be chosen for step 1 of the level-up process. That they are classes designed to gradually replicate the features of a powerful race or template is, for this process, irrelevant.
- As they so often are, dragons are an exception here. As nijineko’s answer demonstrates, under certain circumstances, a dragon PC not only can, but “is required to devote a level every few years to its dragon ‘class,’” per Draconomicon. Even here, though, this is treated as a kinda-sorta class level. It certainly doesn’t apply outside of dragon PCs who have reached a new age category.
Creatures with low or no intelligence must advance by HD
Intelligent creatures that are reasonably humanoid in shape most commonly advance by adding class levels.
[…]
nonintelligent monsters, can advance by increasing their Hit Dice
(Monster Manual, pg. 290)
a high enough Intelligence (minimum 3) to gain class levels
(Monster Manual, pg. 293; note this is in the Level Adjustment section, which is annoying since is the only mention of the Int 3 minimum in the core rules that I can find)
Intelligent non-player creatures can probably do either
The rules say that intelligent, “reasonably humanoid in shape” creatures “most commonly” advance by class, but that doesn’t say they can’t advance by HD. The description of advancing by type says that that creatures that are “not humanoid in shape” or “nonintelligent” “can” advance by HD, which isn’t the same as “must.”
On the other hand, there’s an argument to be made that just because intelligent, humanoid creatures “most commonly” advance by class, doesn’t automatically mean they can choose to advance by HD. Nothing says they “can” do that, the way the rules say nonintelligent or non-humanoid creatures “can.” Likewise, nonintelligent or non-humanoid creatures “can” advance by HD, but nothing says they “can” alternatively advance by class.
Ultimately, though, these are DM-facing “rules” that are more like guidelines in the first place. Monster advancement is a very open-ended section of the rules, with lots of suggestions for DMs for how they can do things but still left pretty open. And if nothing else, there’s always rule 0.