After reading through the comments on A Red Velvet Affair, it seems that there is a lot of curiosity and/or confusion about red velvet cake and its origins. Though, as far I know, nobody has managed to verify the cake’s exact genesis, here is what I have pieced together from my own observations and research.
Apparently dating from around the first third or so of the 20th century, sort of the heyday of the homemade layer cake—when chemical leaveners and hydrogenated fats were widely available; finely-ground, moisture-loving cake flour had been introduced; and the electric mixer was making its way into more homes—right before the advent of inexpensive packaged mixes, there are a number of recipes for American-style cakes * known simply as "velvet cake." These cakes (like most red velvet cakes) were neutrally flavored, meant primarily as moist, rich vehicles for sweet icings.
Many of the recipes that I've found for velvet cakes avoid the use of cake flour, using instead all-purpose flour cut with cornstarch, potato starch or cocoa in order to mitigate the more firm, coarse protein structure of the regular flour and achieve a finely textured or "velvety," moist cake. My guess is that those velvet cake recipes which utilized cocoa in this way—as a tenderizer, not as a flavoring agent—are the progenitors of the red velvet cake that we know today.
There are two types of cocoa powder: natural and alkalized. Natural cocoa powder reacts with acids, such as those found in buttermilk—a common ingredient in layer cakes, to turn a reddish, mahogany color. Alkalized cocoa powder (also known as "Dutch Process" or "Dutched" cocoa) does not react to acid, it just stays brown. So the theory goes that as the use of alkalized cocoa became more common (and, I dare say, the availability and affordability of artificial coloring increased), food coloring was introduced to the mix to replace the reddishness, until, eventually the red was no longer just a shade to recreate a rosy cocoa hue but a thing unto itself.
As an aside, the same cocoa-acid reaction is often addressed as a possible source for the name of "Devil's food cake", though in this case, it seems more likely that this very chocolaty, tender cake was named in cheeky opposition to the pure white, spongy "angel food cake."
One other theory that I've heard about the evolution of red velvet is that at some point (possibly during the Civil War), a sugar shortage in the South forced bakers to substitute the sweet juice of red beets for some of the sugar in their creations. If this theory were indeed true, would there not be more recipes for arbitrarily red baked goods floating around today? Also, red beets are just not all that sweet (true, there is beet sugar, but that's 1) white, not red, and indiscernible from cane sugar and 2) made not from red beets but from sugar beets, which, I understand, are not red at all and are rather unpalatable prior to refinement). There are certainly some older recipes that exist for chocolate-flavored cakes where red beets are used to add moisture and to augment the flavor of the chocolate, but not really to add sweetness.
It is, however, likely that beet juice, which as many of you pointed out is a natural alternative to artificial red food coloring (though it imparts a more maroon, less crimson, hue), was added under certain circumstances to velvet cakes purely as a colorant.
* European bakers largely eschewed the use of chemical leaveners, which are central in creating the texture and loft of our layer cakes, preferring instead the natural leavening power of beaten eggs for their cakes.
A Red Velvet Affair