Try "Purple Power" degreaser from the automotive aisle in Wal-Mart. Use it with a nylon bristle brush, and hot water. It's $5 for a gallon. Works well taking cosmoline and grease out of military surplus rifles and thier stocks.
It's not toxic in the skin contact or inhaled fumes department since it's basically just a really, really, aggressive detergent, but I reccomend wearing gloves since it will chap your hands badly since it sucks away the oil from most anything.