Non-beet alternatives to standard red food dye
Red Velvet cake originally was a reddish brown from the natural processed cocoa (not Dutched) reacting with the baking soda.  You can still make red velvet cake this way, but it will not have the glowing hue that dyes create.  

You have to be sure not to use Dutch-processed cocoa powder as this has been pH neutralized and it is the acidity of natural cocoa powder that helps it retain its red color (which is caused by anthocyanins in the cocoa).  Using buttermilk as the liquid in the recipe will help keep the environment acidic enough to be hospitable for the red coloring.

Hershey's and Nestle both sell natural cocoa powder.