Starting wars does
not in fact require parliamentary approval.
In 1999 Blair used "Queen's Consent" (the notional requirement that consent of the monarch must be sought in order to substantially alter their powers, but in practice these are government powers and so consent is sought from the government) to get rid of a Bill that would actually have required this, the "Military Action Against Iraq (Parliamentary Approval) Bill".
This isn't because Blair couldn't have won a vote and disposed of the bill but because he knew it would be embarrassing and indeed the embarrassment anyway resulted in the (non-binding) Approval bill you cited which has 412 Aye votes.
Even having a vote ("Division") is embarrassing. It forced Labour members who might have told their electorate over and over that they oppose war to choose, stick by their principles that war is abhorrent, and risk deselection for coming out against the stance of their government and many populist pro-war newspapers, or, bend over, vote for the government and hope voters forgive them when it inevitably all goes wrong.
Now, ultimately Parliament is sovereign and so you can argue everything "requires parliamentary approval", but only in sense that silence signifies approval because as a sovereign entity it could intervene but it does not.
If Parliament really didn't want the UK to go to war it can in principle get rid of the Prime Minister and install one who won't start a war. If the Speaker tries to stop them (e.g. by refusing to recognise a member who stands to propose "That This House Has No Confidence In Her Majesty's Government" so as to bring down the Prime Minister) the Commons can convene "The Committee of the Whole House" which is identical to the Commons except that they're picking who runs things, whereupon they can get rid of that Speaker, choose a new one, reconvene the Commons and call No confidence. But it isn't going to do that in fact.
Even for Brexit, while there was majority opposition to the obviously disastrous "No deal" plan, there was no majority in support of any other definitive course of action, including replacing the Prime Minister, all that was done was more kicking of cans down the road, until there was no more road.