I am arriving in Doha at 4:30 in the morning for a 12:00 connection. Should I go out to the city or would I be better off just waiting at the airport?

A bit of shopping at the airport really (and a lot of construction and lines), otherwise, nothing else to do. Not sure how crowded it is at 4:30 a.m. at Doha airport. Then again, not sure what you can do in the city around that time of the day.

Are you flying F/J? Without lounge access, you will probably get bored to death at DOH.

Cheers

Even if you have lounge access, if the lounge in question happens to be the "Oryx Lounge" then this will only stave off death by boredom by about 15 minutes. This has to be the dullest airport lounge I have ever experienced, not helped by the enforced sobriety from the "soft drinks ony" policy.

To the OP if you have not experienced DOH before you could comfortably fit the entire airside terminal within the space occupied by the World Duty Free shop at LHR T4.

Buy a PSP, watch a few movies and play games... That's what I did on a recent trip to Delhi (with about a 5 hour layover in Doha). The lounges (both first and business) are nothing to write home about, but at least you will have a place to sit down and relax away from the hussle and bussle of the terminal. And for some strange reason, the business lounge is a lot larger than the first class lounge (at least it seemed that way to me).

^ Exactly what I was thinking. Even though the lounges won't provide much entertainment, they will prevent you from being stuck in crowds for your entire transit

Cheers

If you decide to go out of the airport, first check if you can get a visa (depends on nationality). If yes, it cost a few dollars and can be had on arrival, paying by credit card. At that early time in the morning the best thing to do would be to go for a long walk along the Corniche - 7km seafront walk.
A taxi will get you there in less than 10 mins. Early morning temperatures are in the high teens, low 20s (C). The biggest mall is called 'City Centre' and is at the far end of the Corniche from the airport, about 20 mins by taxi, but not sure what time shops open there - it may not be until around 10.
Otherwise if you want early morning shopping, ask for the 'new old Souq' area which is only 10 mins from the airport.

Go to the Qatar E government site, get a transit visa and definately leave the airport. There will be zero open that early and your only time killer will be a walk on the corniche along the water or a visit to 'City Centre' the city's largest and most modern shopping complex. I'd wait in the lounge for an hour or so then leave. The lounges as with the airport will be terribly boring but go through the duty free area and shower n rest in the lounge before u leave. Good luck.

Definatly try to get out of the terminal!

I'd second the walk along the corniche. There is also a small park at one point (if you walk away from the water and cross the road) about half the way around, which houses an art gallery. Although the gallery will be closed the design of the park area is nice - lots of water flowing along channels like swimming pools and nice lighting etc. nice enough to pass the time anyway.

If it's open, there is also an ice rink (made of plastic I think) in the City Centre mall - but at that time it's likily to be closed.

The Sheraton hotel is at the far end of the Corniche. If you walk all the way around it should be easy enough to get a taxi back to the airport from there or/and have a rest in the lobby.

Oh, and from my experience, the modern, clean and expensive looking taxis (turquoise and silver coloured) tend to be cheaper than the orange and white cheap and old looking taxis!