Paradox in applying Newton's second law Suppose I apply two vertical but opposite forces with the same magnitude in a body like is shown in the picture:

According to newton's second law, the center of mass shouldn't accelerate, since the sum of the forces in the system are zero. However, I believe that in the situation shown in the picture the body would start rotating around a point which is not it's center of mass, hence, the center of mass would accelerate.
What is wrong with my reasoning?
 A: No ,the centre of mass would not accelerate,the object will rotate about the centre of mass.
If the object is on a table(or anywhere here on the earth) and if you apply the forces as shown in the fig it may not be rotated about the centre of mass because of the frictional forces acting on the object,but in space where there is no friction the object will rotate about the centre of mass.
A: This apparent paradox is actually not a paradox at all. Infact, it is because of Newton's second law, that we can say that the object will rotate exactly about it's centre of mass. This is true for any body on which net external force is 0, but net torque is present.
In Newtonian mechanics, centre of mass serves to simplify calculations, for exactly the reason above.
Although I can understand you thinking that the object will not rotate about the centre of mass, this opinion has no mathematical or logical ground.
A: 
 This is an attempt to answer your question in a somewhat more mathematically rigorous way, but still counting on your (physical) intuition.

As other posters have noted, the linear or translational momentum will not change when you apply the force in a way you described. This is made most apparent by observing the (non)movement of the centre of mass, but you can also 1) split the object into smaller parts, 2) draw vectors of acceleration and velocity of each, and  3) notice that the latter sum to zero. Since (linear) momentum is directly proportional to velocity, the total momentum also equals (and stays) zero. Newton's second law is therefore satisfied.
When dealing with objects that are not point-like, i.e. dealing with anything in other than just one dimension, you can define what turns out to be a useful quantity, angular momentum: $\mathbf{L}=\mathbf{r}\times \mathbf{p} $, where $\mathbf{r}$ is a position vector of a particle (or a part of a larger object, if you treat that part itself as point-like) and $\mathbf{p}$ its linear momentum.
In one dimension, the cross product as a mathematical operation is not defined and does not make sense, whereas for a point-like particle, $\mathbf{r} || \mathbf{p} $ are always parallel, so the cross product is zero. The angular momentum only makes sense then when dealing with (usually 3D) objects of finite size.
If you now repeat the process of splitting your object up into smaller parts and drawing the relevant vectors and the cross-products, you will realize the sum of angular momentum components does not actually equal zero. It is still conserved, however, so Newton's second law is generalized in that regard. Conservation of angular momentum follows directly from the conservation of linear momentum, simply noting its definition and calculating its derivative.

 For convenience only, torque is usually defined in this context as $\boldsymbol{\tau}=\mathbf{r}\times\mathbf{F}$, but this is simply to ease notation.

A: Newton's Law, when applied to rotating systems such as yours, are different than the translational law you're probably used to seeing.  The 2nd Law is 
$$ \vec{N} = \frac{d\vec{L}}{dt} = \sum_i \vec{r_i}\times \vec{F_i} $$
$\vec{N}$ here denotes torque, which is equal to the time derivative of angular momentum.
$\vec{r}_i$ are the position vectors from the axis of rotation to the forces being applied, and of course, $\vec{F}_i$ are the forces applied.
Hence, what you have here is much like when you add up the translational forces acting on a block on a ramp, or something similar.  Here you simply see which is larger, $\vec{r}_1\times\vec{F}_1$ or $\vec{r}_2\times\vec{F}_2$ and the larger torque will induce angular acceleration in the direction of the torque.  
