Well, my friend, I think you face an uphill battle if you try to play by the rules.

Generally, a) to have a valid Russian passport good for travel (e.g. renewal), you need to have an unxpired Russian external passsport. If it is expired, you are out of luck. b) you can't get a Russian passport and prove that you are a Russian citizen, if you don't have a USSR passport as a "conversion case" from a USSR citizen to Russian Citizen that people quoted above. c) you don't have a USSR passport as you were only 4 years old. Your info (picture, data particulars) were probably inserted into your parents passport at the time they left the country.

I think you will be in the world of hurt trying to get that Russian passport. I think at best you'll have to somehow try to get a proof of Russian citizenship (I don't think Russian birth certificate is sufficient in this process) and then pay mucho dinero to get a "Permission to Return". That Permission only lets you get into Russia where you'll have to sort this out to get a real passport. (Can't leave the country with it and can't leave on your US passport because you didn't enter under a visa). Logically, you then would go to the location where you and your parents used to live prior to leaving - good luck with that.

A co-worker of mine faces somewhat similar situation. So, to avoid the hassle, she gets Russian visas with her US passport through some travel agency connected to NYC Consulate. I can get a name and PM it to you. Expensive and legally shady, but it works for her.

Let us know what Houston Consulate advises you to do.