I've tried a few solvents, notably:
Acetone - dissolves most grease based gunge. It's also miscable with water so you can rinse coins in distilled water if desired.
Isopropyl Alcohol - Acetone is better, IMO, but this works.
Limonene - This is degreasing agent widely used in cleaning electronics. It's the orange smelling stuff you use to clean heatsink gunk off CPUs, for those familiar with it. It works, but it's very, very smelly and has no discernible advantages over acetone.
Ammonia solution - Probably the strongest cleaning agent for grease based stains; you can rinse coins off with distilled water. It won't react with silver or gold, but it will form cuprammonium complexes from copper salts. I've never tried it with copper coins.
I got a little borosilicate petri dish and lid off Ebay. This lets you immerse a coin with about 10ml of solvent and pop the lid on it (good for anything that produces fumes). I also got a 10ml pipette for transfering solvents into the dish. Usually soaking in acetone and/or ammonia solution for a few minutes is enough to dislodge most gunge and bring the coin up nicely.
One thing I did consider is getting a water pik toothbrush for rinsing and using distilled water for the rinse.