Note that you can keep increasing Vcc while keeping the same Vce and Ic. Rc goes up, and Av goes up proportionally, until Early effect ultimately limits gain*.
This breaks the Vcc/2 assumption, which is how the original question can have such a well-defined answer.
This approach has been used in audio amplifiers before, using an excessively high supply voltage to enhance gain, as well as provide more dynamic range. A transistor biased at 30V and supplied from 100V has triple the gain and twice the dynamic range of a transistor supplied from +/-15V. Dynamic range being the available voltage swing before clipping occurs.
*Which can be extended further by keeping collector voltage constant: if you use a cascode configuration, the effect is to isolate the output voltage (which is driven by the top transistor) and current (which is set by the bottom transistor), giving a more ideal CCS output. You need to do the same for the load, of course, so instead of a very large resistor, you'd use a current source, which either uses a fairly large emitter resistor (in a sense, cascoding the resistor with a transistor, to make it a better current source -- same idea
), or two transistors in cascode proper. After these steps, the DC gain is now extremely high (easily over 10k), but very weak (if you connect any resistance to it, the gain drops like a stone), and very slow (because the capacitive reactance of the transistors themselves dominates, even in the audio frequency range).
Tim