Hagrid is seen all over the country throughout the series. Normal wizards travel by apparating, floo powder, brooms, and (occasionally) muggle transportation.
Hagrid appears to big to use the floo network, he can't ride a broom, and cannot legally apparate. So how does he get to London from Hogwarts which is located in Scotland?
The only transportation Hagrid is ever shown to use in canon are:
Sirius' flying motorbike (in PS when he delivers baby Harry to Privet drive, and DH during Battle of Seven Potters);
Muggle subway in PS when he takes Harry to Diagon Alley. However, that was a new experience for him: Although Hagrid seemed to know where he was going, he was obviously not used to getting there in an ordinary way.
However, we can add to your list the following possibilities:
a possibility of MoM portkeys - while it's not detailed in book canon, my impression from Pottermore is that portkeys are definitely used for travel to preset destinations (and if the MoM would schedule portkeys available to the public, it'd be to London where MoM is).
Knight Bus
Finally found a quote proving that!
'Buckbeak's case against the Committee fer the Disposal o' Dangerous Creatures,' said Hagrid. 'This Friday. Him an' me'll be goin' down ter London together. I've booked two beds on the Knight Bus...' (PoA, Chapter 14, "Snape's Grudge")
Apparently, he flies to places - it's unspecified how, but presumably said-same Sirius's motorbike (except, where was the motorbike when he and Harry were leaving? No clue)
"How did you get here?" Harry asked, looking around for another boat. "Flew," said Hagrid.
"Flew?"
"Yeah -- but we'll go back in this. Not s'pposed ter use magic now I've got yeh."
They settled down in the boat, Harry still staring at Hagrid, trying to imagine him flying.
(PS)
While I seriously doubt Hagrid could fly a Thestral {{update: as per @MacCooper, he said explicitly the weight was too much in DH: We'll be on the bike, brooms an' thestrals can't take me weight, see }} - or even try riding several, he'd be concerned for the animal's well-being - he could likely ride an Abraxan non-invisible winged horse, at least when/where Muggles can't see him.
'Yeah, tha's right. Over . . . over a friend's broomstick. I don' fly, meself. Well, look at the size o' me, I don' reckon there's a broomstick that'd hold me. Friend o' mine breeds Abraxan horses, I dunno if you've ever seen 'em, big beasts, winged, yeh know, I've had a bit of a ride on one o' them an' it was ' (OotP, reply to Umbridge)
In addition, while you stated that Hagris is too big to use Floo network, I'm not entirely certain that this is canonically proven. While it MAY be true, it MAY also be that wizarding fireplaces connected to Floo are enchanted to magically enlarge if a large party (of several people, OR a half-giant) show up. This is pure speculation, I don't think we know one way or the other from canon.
He uses magic :D
Now seriously, He might still use Sirius' flying motorcycle since it is shown that he has it in Harry Potter and the Philosopher's Stone and and Harry Potter and the Deathly Hallows.
Also he uses magic to enhance normal muggle vehicles like speed up boat in Harry Potter and the Philosopher's Stone.
He can also use Knight Bus.
Not to mention that there is a possibility of flying a Hippogriff, using a portkey or even Fawkes. He also might used multiple Thestrals to support his weight.
