Creatures like dragons start with four hit die and those hit die provide them with enough power to classify for several prestige classes. Can such a creature select a prestige class before getting a base class?
Yes. (It's a long post.)
From the "Improving Monsters" section of the 3.5 rules:
The creature’s Hit Dice equal the number of class levels it has plus its racial Hit Dice. A creature’s "monster class" is always a favored class, and the creature never takes XP penalties for having it.
So in that sense, monsters always have a class -- the "monster class" whose features are defined by their type and HD. This section also says,
If a creature acquires a character class, it follows the rules for multiclass characters.
And those rules say,
A character may add new classes as he or she progresses in level, thus becoming a multiclass character. The class abilities from a character’s different classes combine to determine a multiclass character’s overall abilities.
One more should do it! From the Prestige Classes section:
Prestige classes offer a new form of multiclassing. Unlike the basic classes, characters must meet Requirements before they can take their first level of a prestige class. The rules for level advancement apply to this system, meaning the first step of advancement is always choosing a class. If a character does not meet the Requirements for a prestige class before that first step, that character cannot take the first level of that prestige class.
So breaking all this down, we find that:
- Monsters HD are exactly the same thing as "levels in a monster class" for rules related to advancing that monster.
- Prestige classes follow the multiclassing rules, except insofar as they have requirements which must be met before a level in the class can be taken.
- Taking a class level (in any class, prestige or otherwise) follows the rules for multiclassing as a monster.
So, as long as the monster meets the requirement for the PrC at the time they would choose a new class level, then yes. The rules are 100% explicitly clear.
For additional reference, this answer details the process of gaining a level.