Also I'm interested in the best players who have played the Nimzo frequently, who I can search up in my database?
Creating my Nimzo-Indian Repertoire?!

You should not prepare an opening with a database, especially not one so complicated such as the Nimzo.
Having a repertoire is not as simple as "I like this line, I'm going to play this and that". All your lines should be combined together to have common theme and plans...that's the only way you're gonna learn them efficiently.
Also you'll need to find a companion to the Nimzo in case white plays 3.Nf3 and it would really help if, again, you had similar plans.
I got my Nimzo - Bogo repertoire from Dzindzi's book. I really liked it, it was written with simplicity and easy-to-study in mind. It doesn't have your line though, against 4.Qc2 it does 4...Nc6. It pushes d5 only in the classical Nimzo (4.e3) with the plan of leaving white with an IQP.
That's the only repertoire book I've read on this though, so I can't really vouch for its quality.

What does it suggest against 4.a3, 4.f3, 4.Nf3 and 4.Bg5? Those are the lines I need to prepare something against.

4.Qc2: Nc6. Bxc3 when provoked, and then plan is to play d6 and e5, supported by the Q on e7.
4.e3: b6. Against Bd3 I'm eventually breaking with c5. If Na4 then I'll retreat my B and still planning on d6 and a central break with e5 if possible. If Bd2 I take on d4 and then d5, giving white an IQP if I want (still keeping my BB).
4.e3: b6. Against Ne2 I'll go Ba6 and d5 and keep pressure on c4, maybe try to exchange lsB.
4.f3: d5, retreating the B, then dxe4 and e5 quickly, trying to create weaknesses on the dark squares.
4.g3: gaining the initiative with c5, Ne4 and Qa5 bringing pressure to the pinned N.
4. Bg5: h6 and c5, trading my B doubling white's pawn and setting up mine on e5, d6 and c5 (keeping centre closed)
4. Qb3: c5 and Nc6, having a better version than 4. Qc2, because I can play Ne4.
4.Bd2: just castle, then give up my B for the N but attacking with Ne4, getting back white's dsB. With 2 minors traded I won't have problems of space.
4.a3: simply double white' pawn and play against the weak c4 with Ba6, Na5.
Many times I don't like Dzindzi's suggestions either. There are chapters of that book that I avoid. But I really like his repertoire with Nimzo and Bogo.

Using the DB is OK to get a feel for openings and variations, but a book on the opening would be better, esp since most DBs seem to consist of unannotated games. GM Emms "The NID Move by Move" is pretty good, although it's not as comprehensive as ECO or a DB since it's a learning tool although it is pretty up-to-date and covers most of the main lines - and in many cases the ones Emms likes, although I don't have a problem with that (so far)
Emms goes thru entire games played by world class GMs with frequent "pauses" while he asks you to consider why some moves are made and others aren't, so he forces lazy guys like me to think about what they're doing (or trying to do) when they play an opening.
Personally though I think you should get something like "Fundamental Chess Openings" which will give you the basic ideas and concepts of all major openings and/or MCO-15, which is much more comprehensive but much less instructive, but still a lot better than just going thru oodles of unnanotated DB games since every opening has a brief historical/analytical introduction and the lines shown are representative of, well "Modern Chess Openings" FCO is still my first choice however
I kind of like the DVD from Jacob Asgaard (http://www.chessbase-shop.com/en/products/the_nimzoindian_defence-the_easy_way)
It is aimed at people starting with the Nimzo so it is not a diarhea of moves and variations other Nimzo books and dvd's often give but focuses more on the ideas in certain positions. He has a very decent rep selection often giving a save but more boring approach (against the high rated players) and a more risky approach

I kind of like the DVD from Jacob Asgaard (http://www.chessbase-shop.com/en/products/the_nimzoindian_defence-the_easy_way)
It is aimed at people starting with the Nimzo so it is not a diarhea of moves and variations other Nimzo books and dvd's often give but focuses more on the ideas in certain positions. He has a very decent rep selection often giving a save but more boring approach (against the high rated players) and a more risky approach
Is this a complete explanation of the Nimzo?
The book I was talking about is only a repertoire for black. I'm an e4 player so I don't need to know theory of the Nimzo from white's perspective (even if I would surely benefit from it).
It is a black repotoire book. It gives a variation (and sometimes 2) against the most common setups used by white. It is good because it focuses more on the ideas and the plans instead of concrete moves etc.
If you like a complete explanation of the Nimzo I suggest Sokolov's excelent book the strategic nimzo indian (http://www.newinchess.com/The_Strategic_Nimzo_Indian-p-969.html) advice rating is 1800+ for this on though perhaps even 2000ish

I play the sicilian and the symmetrical english, so against 1.Nf3 I can just answer with c5.
Not really sure what you mean though: if I answer 1...Nf6 we'll either get into a Bogo after d4 e6 c4 or it will be one of those pesky systems like the Colle, London, etc.
Unless you mean white playing the "closed" english with Bg2, where I would like my knight to be on e7 instead of f6. That's why I should play 1...c5 first. I don't think it's such of a big deal though...

So what do you all believe the most dynamic and interesting ways for black to meet 4.a3 and 4.f3 are? These are the variations that annoy me

Against 4.a3 you can take on c3 (of course) and then play against the c4 pawn by ...c5, ...b6, ...Ba6 etc.
Against 4.f3 the most reliable mainline is 4...d5 5.a3 Bxc3+ 6.bc3 c5 7.cd5 Nxd5 8.dc5 Qa5 9.e4 Ne7 (that's what I'm playing, anyway), but I may have to change that, since against a booked up white this is almost certainly a draw...

4. a3 is simple. Bxc3!, b6, Ba6 (pressure on c4), Nc6-a5, when prepared c5! (remember some tricks with dxc5 Nb3, hitting the rook, take back on c5 with knight and have alot of pressure on the halv-open file.
I think the Move-by-Move book is very good in that chapter. It also shows the instructive ... d5!! if white is pinned down on the c4 pawn, trading a weak pawn (on c4) to a weak square (c4). Castle late, since white will then find it harder to attack.
Against 4. f3 you can get a slightly worse 4. a3 system with 4... 0-0, where you'll have to play Ne8!! before white has time to play Bg5. (since it's dangerous to break the pin with h6-g5.

Okay so against a3 I will pile on the c-pawn, does anyone have any thoughts on the variation 4.f3 d5 5.a3 Be7!? Anand has played it and won with it (admittedly in a blitz game) so it can't be that bad. Otherwise I think I will go with the variation you mentioned pfren.

Karjakin and Leko recently played 9...Nf6 (instead of 9...Ne7) but I have not looked at this move at depth- I always had the impression that e7 is the right square for that mule.
If you want something unusual, you can look at the interesting sideline 4...c5 5.a3 Ba5!? which was recently played by the Istratescu and Parligras with good results.
Another solid, yet ambitious line, is 4...0-0 5.a3 (5.e4 d5! is apparently fine for Black) Bxc3+ 6.bc3 Nh5!? which is scoring quite well.

I liked a lot The Nimzo-Indian explained (Reinaldo Vera), but it goes so deep in the details of some lines I am not sure it is fit for you, and maybe a few lines are outdated since.
But basically, 4.a3/f3 is almost the same system, and the easiest to play as Black. Black's plan is more or less to pay within ten moves ...b6, ...Nc6-a5, ...Ba6, etc. You can see there the real idea behind the Nimzo-Indian : trading the pair of bishop for a small plus in development and weak pawns/squares. White obviously has some play against the king, but that's him who miust find the good moves before being strangled.
I fear much more 4.Qc2 or 4.e3, in the first case White might force you to take the initiative against something else, and you must do something with it, and the second case aims to develop as soon as possible to prevent 'normal' NI play.

I have recently won a funny game (as white) in a well-known theoretical line of the Qc2 Nimzoindian. White's pawn sacrifice is quite dangerous, and after a couple of inaccuracies Black ended up resigning in a position where he is in a zugzwang situation. However, I think white has nothing if Black opts for the less well known, but safer 14...Nd7 (instead of 14...Bd6).

Haha nice game!
@Irontiger, that's funny because I find the Qc2 and e3 lines much easier to play than the f3/a3 lines!
I don't think I am going to try playing c5/d5 against the f3 line because I don't really think I understand the positions very well. I think I'll prefer piling up on the c4 pawn.
@pfren 4...c5 5.a3 Ba5 looks very interesting, I think I will have to look into it a bit more later
I'm not too sure on 4...O-O 5.a3 Bxc3 6.bxc3 Nh5, I think after 7.Nh3 white has a large central presence and I'm not sure what Black should do with his lead in development, becuase white is just going to play e4-Be2 and O-O
Anyway what of the 4.f3 d5 5.a3 Be7!? variation? Here is Anands game with it
So, I've just decided I'm going to play the Nimzo-Indian Defence because I like the variations after...
However I am very new to the Nimzo and I'm not sure what I'm going to play against 4.a3, 4.f3, 4.Nf3 and 4.Bg5. I am looking for variations that have good winning chances and that give interesting and/or dynamic play.
Any recommendations on what I could try against these variations( 4.a3, 4.f3, 4.Nf3 and 4.Bg5 or any other critical variations that I need to know) are appreciated!