You check prerequisites when the character is completed.
Although the PHB separates character creation into 6 steps, rarely are the steps done in isolation. Similar to concept of Simultaneous Turns, the steps provide a process for determining many simultaneous selections. In other words, choices made at each step generally reflect choices you will make at other steps.
Most feats are written with the complete character in mind; ie, added to a character after creation. Thus, prerequisites only come into play for the complete character. As long as the completed character meets all prerequisites, there is nothing preventing you from selecting a feat before you select the class/ability that satisfies the prerequisite.
You have forgotten the most important step 0 (emphasis mine):
Before you dive into step 1 below, think about the kind of adventurer you want to play You might be a courageous fighter, a skulking rogue, a fervent cleric, or a flamboyant wizard.
...
Once you have a character in mind, follow these steps in order, making decisions that reflect the character you want. Your conception of your character might evolve with each choice you make. What's important is that you come to the table with a character you're excited to play. (PHB p.11)
In short, character creation is done as a whole. The steps simply help organize your decisions. Similar to the concept of simultaneous turns, there is nothing preventing you from selecting a feat if you know you will meet the prerequisite with a choice in a later step.