When adding new levels of an existing class or adding levels of a new
class (see Multiclassing, below), make sure to take the following
steps in order. First, select your new class level. You must be able
to qualify for this level before any of the following adjustments are
made. Second, apply any ability score increases due to gaining a
level. Third, integrate all of the level's class abilities and then
roll for additional hit points. Finally, add new skills and feats.
The order of how you level matters. You're allowed take a feat the same level you gain the prerequisites only because gaining feats is the last thing you do. If the prerequisite is a skill, spell, or ability, you already have it by the time you take the feat.
Of course, if the prerequisite is another feat, you must already have the prerequisite feat before you can take the desired feat. However, since character advancement is an ordered process, if you gain multiple feats in a level1, you can choose to take the prerequisite feat first. You can now take the desired feat.
In your example, you can take neither feat first since neither feat has its prerequisite met.
1 Class abilities that give bonus feats give them at the time you normally add new feats (after skill points). It's unclear if you choose your standard feat before your bonus feat or vice versa, but I would generally allow players to select feats in any order if it matters.
Yes, you must meet the level requirements for fighter bonus feats.
Fighters get to take more feats than other classes. Everyone gets a feat at 1st level and every 3rd level (so 1, 3, 6, 9, 12, 15, and 18), but fighters also get additional feats at 1st level and every even level (so 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, and 20).
In both cases, you need to meet all requirements for the feat you pick. Fighters don’t let you take feats more easily or anything, they just let you take more feats.
Now, Weapon Specialization et al. specifically require Fighter levels as part of their requirements. Whether you take them as a fighter bonus feat or as a regular feat, you can only take them if you have that many fighter levels. These are the only feats that are unique to fighters; every other feat a fighter can take, someone else could also take.
Anyway, long story short, as a Fighter 3, you could not take all of these feats. In fact, you could not take any of them, because they all require 4 or more levels of Fighter.
Now, that said, you should know that these are very weak feats. Weapon Focus is commonly used as a “tax” to get into prestige classes, and can be valuable for that (but not for itself), but the rest rarely are, and are therefore basically worthless. I strongly recommend that you do not take them. The only exception is Weapon Supremacy, which requires all the other Weapon Focus type feats from both the Player’s Handbook and Player’s Handbook II, plus Fighter level 18th. That feat is very good. It also comes way too late and requires way too many poor feats.
And since the fighter-only feats are bad, and everyone can get the other fighter feats, this winds up making the fighter a pretty poor class. Fighter 2 is OK; a feat every level’s kind of useful, though usually only those who are really desperate for feats should really go that route. But after that, the fighter class offers very little. Therefore, I strongly suggest multiclassing, taking some fighter levels, some barbarian levels, maybe some ranger levels. Horizon walker’s a pretty good prestige class. Basically, you take Fighter when you need a feat; you don’t take Fighter just because and then figure out what feat to get.
The Forgotten Realms Campaign Setting (3.0) has a list of Regional feats and the Players Guide to Faerûn (3.5) updated that list. Unless I am mistaken a single Regional Feat along with a single Racial Feat are available but only at 1st level.
In addition, certain classes have automatic Feats at 1st Level. A fighter and a Human get insane feat bonuses. The DM II also had the Woodsman Mentor (p. 178) which gave a limited Track Feat, but of course you would then need to take the Apprentice Feat first, unless you use this for a zero-level character HouseRule or something.
There are a number of ways you get to take more than one feat at first level.