In my mind such a game can be made to be quite simple.
If you limit the game to one kick move and one punch move per character, two characters, and one special move per character this is within the reach of any person new to gamedev and possibly only as complicated as maybe something like Tetris or at most a simple platformer.
You could also keep the animation frames to a minimum, use existing graphics from free resource sites to get the ball rolling, and this would give you something to build off as you learn.
The main thing is to remember the age old adage "Keep it simple". You can always make incremental changes to your game after you have something working, rather than trying to do everything all at once. Big plans up-front are a dinosaur from the past for most developers and agile methodology can be applied (google it if you're not sure, Tbshirk) which makes game development much easier.
Please let me know if you have any questions!
I don't really agree with you here, nor do I see any advice for the OP to make this game. How do you propose a brand new programmer make SF2 clone as his 1st game?
If you're brand new to programming, then you're just not going to be able to make a SF2-type game right off the bat. You need to understand the basic of programming 1st, then understand how games in general can be programmed, and doing simple, no animation-type games with a single screen is a great start. Pong, Breakout, and then you can throw in some animations when you get an idea how animation works.
Python and pygame should be fun to program, and fun to learn to make games.
Good luck and have fun.