Well, if you want 4 channel and Traktor, a (used – seeing what your budget is) S4 seems the only viable option.
On the other hand, you are claiming the SB and the MC2000 are lacking features you think you need. But you don’t tell us which features those are. Also you say you want to do more and explore more options, yet you say you don’t want performance pads (a great way to get a lot of functionality into 8 buttons).
Finally you say you need 4 channels so you can mix two while you have two waiting? The whole idea about 4 channels is that you can mix MORE than two tracks at once and/or use more different sources (I have two mediaplayers hooked up to my channel 3 and 4 for backup purpose and to play CD or USB-stick material if necessary).
As for the units you mention, my personal opinion is to stay away from Gemini (but I know we have readers that disagree with that opinion). Vestax is gone, so buy one at your own risk (drivers might be hard to find and support is non-extinct). The Beatmix 4 is a good controller as is the MTQ.
I would not toss the idea of two-channel starter controllers though, especially considering that you will be spending at least 100 dollars out of an already limited budget on getting the software. So, unless you buy used, the higher end (and most 4-channel) controllers will be out of reach.
Just my two cents as usual.