I would avoid anything acidic, even water with a pH down near 7 can be aggressive towards the travertine. I mentioned steam cleaning and I was actually kind of serious about it. I have a steam cleaner (the kind with a wand, not a carpet cleaner) and it is very useful for pulling up organic stains as opposed to trying to use something caustic to lift an organic stain. I actually use it a lot on my BBQ to remove oils and greases that build up on it as well clean outdoor tiling with it.
One other option, although difficult to find, would be to use a high concentration form of peroxide to bleach the stains. You would want about 10-12% peroxide mixed with a few teaspoons of ammonia (straight ammonia, no lemony or pine scents). The ammonia raises the pH of the solution and de-acidifies the peroxide (peroxides are stabilized at low pH typically less than 5). The ammonia will help to lift and dissolve greases while the peroxide will bleach organic staines. Using peroxide & ammonia avoids the use of chlorides which can be detrimental to the stone over time. 27% peroxide solutions can be found at pool stores that sell Baquacil products as the peroxide is used as the oxidizer in Baqua-pools.
Just be careful handling high strength peroxide as it is a bleaching agent and it will bleach skin. Like all chemicals, you want to wear gloves and eye goggles, and long sleeved clothing to protect yourself.
