But, what if the Initialization vector is computed with some number of random bits and then some counter. For example, 12 bytes of random data plus 4 bytes of a counter?
That's still relatively secure. Block ciphers are random permutations, so as long as the plaintext block XOR'ed with the IV is doesn't collide with an earlier block then no information is leaked.
An analog to the question might be: what would be the damage for generating random IVs, except for that the last 4 bytes are always zeros?
That's indeed analogous. The problem with CBC is that attackers could create a known plaintext attack so that they create an identical initial block so that this block and any identical block that follows it can be detected - if that's required at all; if all of the the IV is a counter and the plaintext also starts with the identical counter then obviously the first input block to the cipher will always be identical, to name one obvious example.
My understanding is that the output of AES is "random-looking"
The keyed block cipher is a random permutation. The construct AES-CBC should result in a ciphertext that is indistinguishable from random to anyone without the key - hence IND-CPA.
Is there any scenario in which using a random number + counter for AES-CBC would be beneficial?
The only advantage I can think of is that you'd require fewer random bytes from the RNG, which also don't need to be transmitted.
If those randomized bits - XOR'ed with the plaintext bits, but the result should be just as random - don't collide then the construction is secure. However if they collide then the chosen plaintext attack may succeed and the construction is not secure anymore. So the counter bits might as well have been set to zero.
Is there a number of constant / counter bytes in an IV at which AES-CBC will start to show weakness, other than the higher chance of an IV collision?
No, it is just about collisions of the randomized bits. And the more you encrypt with a single key, the higher the chances of a collision. This goes for any use of the block cipher by the way. There is even such a thing as multi-target attacks for AES where the keys may differ that, obviously, may have practical drawbacks.
Note that it is entirely possible to use a counter for CBC. However, you'd have to encrypt the counter first using the block cipher, and then use the result as IV then you'd have block for which the bits are hard to predict by an adversary. Obviously such a block might also collide with another block created by the cipher, so if you want to keep everything as secure then you'd use a different key for the block.
This IV will never repeat until the counter runs out, which may be an advantage. The adversary will never learn much about the possible generated IV's either, even though some knowledge is leaked. If blocks don't repeat then obviously those are of course removed from the set of possibilities, but since there are $2^{128}$ of them this won't give the adversary much of an advantage.
I think this scheme is much better if you are able to keep a nonce anyway as it removes the requirement of a random number generator, nor do you need to send the counter. Beware that keeping state is also dangerous in cryptography; a reset of the state is something that should be protected against. You could also use your block and then encrypt that to use it as an IV, but in that case you'd still have to generate & send the random bytes separately. Sending the counter is also an option.
As an aside:
Not looking for a specific answer for this one, but just general insight into the design of AES.
This has absolutely nothing to do with the design of AES. The only thing that matters to CBC ciphers is that the block cipher is secure, and what the block size is. As you can imagine 128-bit block ciphers are much more secure than 64 bit block ciphers such as 3DES in this regard, and there is actually something to be said about using 256 bit block ciphers when it comes to collision resistance.
Final note: CBC doesn't provide integrity nor authentication of messages. If you want to add that you may need to use encrypt-then-MAC, using e.g. HMAC to create an authentication tag. If that's performed then the HMAC should also include any data send such as random bytes or counters / nonces that are used to construct the IV.
Generally we try and use authenticated ciphers such as AES-GCM making this whole answer kind of pointless. Still, there CBC + HMAC is considered pretty secure and fast enough in most circumstances, and otherwise this is a nice learning experience.
