I'm going to agree with @fgrieu's marvelous post above in a back-handed way.
My answer is: No, you don't have to use an HMAC. Do it anyway.
As you noted, some hashes, sush as SHA-3 (especially in its Keccak form), Skein (which I was a team member on), and others will work just fine. In the case of Skein, there is a one-pass Skein-MAC that has a proof of security interestingly done by Mihir Bellare (also a Skein team member), who did the HMAC proof that @fgrieu cited above.
Furthermore, there is an HMAC criticism that I and a few others (including Niels Ferguson, another Skein team member) have made that is that HMAC essentially assumes a working hash function. HMAC protects against a number of breakages of hash functions, including Merkle-Dåmgard length extension attacks, but we don't know how good it is with a hash function with whatever sorts of weaknesses. I don't think we have any idea, for example, how good HMAC-MD5 or HMAC-MD4 is, despite the horrid breaks in each of them. (MD5 is readily broken with a computer; MD4 is readily broken with pencil-and-paper.) You can see that criticism above in @fgrieu's remark about assuming that F is an ideal PRF. What if F is known to be a non-ideal PRF with a whole set of flaws? How good is HMAC then?
You've described a bunch of constructions that are very likely to work just fine with the sort of hash function one is likely to see in the real world, like SHA-1, SHA-256, SHA-512, and SHA-512/z that are still known to have weaknesses. Even better would be a hash of Key-Length || Key || Message-Length || Message.
But do an HMAC anyway, unless you have a need for the one-pass MAC that you can get from Skein or Keccak/SHA-3. As an example of need, the protocol ZRTP allows either a SHA-1 HMAC or a Skein-MAC (again in full disclosure, I'm a co-author of this protocol and perpetrator of this use). The reason is that if you're doing the HMAC, then the majority of the compute time of the protocol is spent in the HMAC. Despite this, it's merely an option with a fallback to the HMAC always being there.
The reason you want to do an HMAC is a meta-principle I've learned in doing crypto: don't do anything that stupid people think is stupid. Think of this as a corollary of the maxim, "never argue with an idiot, people may not be able to tell the difference." That's snarky and pejorative, so let's also call it the Elvis Costello Detective principle, "Don't get cute." So let's look at it from a real-world perspective.
I think that your construct is just fine in any real-world case. But what if we are wrong? Unless someone who is as well-respected in protocol proofs as Mihir Bellare is going to do a proof for this, then we always are behind the you-have-no-proof eight-ball, and it's a fair cop! Even if you point out that these security proofs has their own set of assumptions and are of questionable worth (especially after the Paterson et al. SSH break -- which is another whole discussion), the fact is that there's a proof for HMAC and not for yours (unless you're using a known-good-MAC hash like Skein or Keccak).
I can think of some ways to break that construct through the use of stupid coding. (Here's a hand wave: make the counter be a fixed-length binary counter, as opposed to the ASCII string of the actual length. Wrap the counter so the colliding message has the same length mod 2^n (e.g. 1 vs 257 for a one-byte counter or 65537 for a two-byte counter) and then go on for a length-extension attack.) This is massively face-palmingly broken, but it wouldn't be the first time someone made a massively face-palminingly broken coding error. In fact, such things happen every day.
I have come to believe that an important property of good crypto is being understandable. The advantage that HMAC has over constructs like an improved keyed hash is that the person reading your protocol can say, "oh, it's an HMAC" and move on, rather than having to read all the details and remember under which circumstances those improvements work. Moreover, if you use something nonstandard, people will complain. Those complaints won't go away. Even after you've written a zillion blog posts about how what you did was just fine, people will still complain. Whereas if you use an HMAC, they won't. The cost of the lack of complaints is a mere second call to the hash function. If that mere second call is actually a large cost (like with ZRTP), then there are one-pass systems with proofs of security you can use!
The ultimate problem with what you're suggesting is that you're getting cute. HMAC exists to address known problems with keyed hashes. It has a proof of security that shows that it meets that goal. It has a history of being useful in the field. Even the legitimate criticism of that proof and use-history doesn't bolster the way you're getting cute, and even though I think your cuteness is secure enough, I know I don't have anything other than licking my finger and sticking it in the wind to back me up.
So to sum up, no, you don't have to use an HMAC. Do it anyway.