The referee would stop play and restart with a dropped ball to be taken from where the ball was located when play was stopped (unless the ball was within the goal area - it would then be brought to the nearest point on the goal area line parallel to the goal line).
On p. 74 of the 2014/15 FIFA Laws of The Game (relevant passage in italics):
More than one offence occurring at the same time
- Offences committed by two players from the same team:
- the referee must punish the most serious offence when players commit
more than one offence at the same time
- play must be restarted according to the most serious offence committed
- Offences committed by players from different teams:
- the referee must stop play and restart it with a dropped ball from
the position of the ball at the time of the stoppage, unless play was
stopped inside the goal area, in which case the referee drops the ball on
the goal area line parallel to the goal line at the point nearest to where
the ball was located when play was stopped
In practice this rarely happens, as one foul will usually occur before the other, even if it is by fractions of a second.
The only time I can imagine simulataneous fouls occurring is if two players from opposing teams dive in to win the ball and collect each other instead. Even in this situation, they'd probably have to be facing each other, as a side-to-side collision where both players are using similar amounts of force is unlikely to be seen as a foul.
In the situation you described, most pushing and holding occurs at a corner kick before the ball is put into play. If this is the case, the restart would be a retake of the corner kick.