They're higher-status than Muggleborns but not as high as pure-bloods.
Half-bloods have nowhere near the status that pure-bloods do. Bellatrix tells Harry not to besmirch the Dark Lord's name with his half-blood tongue, calls him a 'filthy half-blood', and is greatly offended and upset on behalf of the Dark Lord when Harry accuses him of being a half-blood as well.
“Yeah,’ said Harry, maintaining his tight grip on the glass ball, expecting another attempt to bewitch it from him. ‘Yeah, I’ve got no problem with saying Vol––’
‘Shut your mouth!’ Bellatrix shrieked. ‘You dare speak his name with your unworthy lips, you dare besmirch it with your halfblood’s tongue, you dare –’
‘Did you know he’s a half-blood too?’ said Harry recklessly. Hermione gave a little moan in his ear. ‘Voldemort? Yeah, his mother was a witch but his dad was a Muggle – or has he been telling you lot he’s pure-blood?’
- Harry Potter and the Order of the Phoenix, Chapter 35 (Beyond the Veil)
However, half-bloods aren't as badly treated as Muggleborns. A wizard charged with being a Muggleborn by Umbridge's Muggle-born Registration Commission said he was half-blood while pleading his case.
“And then, abruptly and shockingly amid the frozen silence, one of the dungeon doors on the left of the corridor was flung open and screams echoed out of it.
‘No, no, I’m half-blood, I’m half-blood, I tell you! My father was a
wizard, he was, look him up, Arkie Alderton, he’s a well-known broomstick designer, look him up, I tell you – get your hands off me, get your hands off –”
-Harry Potter and the Deathly Hallows, Chapter 13 (The Muggle-born Registration Commission)
There don't seem to be degrees of half-blood.
To a pure-blood family, anything less than completely pure is a disgrace. A half-blood is a half-blood, regardless of how pure either of the parents were before. Nymphadora Tonks would be considered just as half-blooded as Tom Riddle, despite the difference between their parents' respective statuses. All four cases in your question would be considered equally half-blooded by wizards who adhere to pure-blood standards.