Looking again at the recipe it sure has a lot of red food coloring and very little cocoa. I think I could even use my Ghiradelli sweet ground chocolate & cocoa I use for hot chocolate, or the old cocoa. One teaspoon doesn't make it work buying something I won't use again for a long time. Is red food coloring still bad for you?
DR Jane - Red Velvet Cake is essentially a "light" chocolate cake that has a lot of red food coloring in it to make it red. Essentially, it's all about the cream cheese frosting.
As for using your "old cocoa", well... Part of the reason the cocoa is included in the recipe is to help with the leavening - chemical reactions and all that. So, if you use "old cocoa" or "hot cocoa mix", it might not turn out. Best to "splurge" on a new can of cocoa powder.
Otherwise, just make your favorite chocolate cake recipe and frost it with cream cheese frosting (sans walnuts).
*And red food coloring is safe to use. -But if you're at all concerned, there are some "natural" red food colorings out there that are derived from beets.