Seis años después, llegué a esta pregunta y casi la decepcioné según la respuesta aceptada. A partir de hoy, no es complicado, utilizando el enrutamiento de políticas. Todos los detalles están disponibles en este mismo sitio, en https://serverfault.com/a/389004/70774.
En mi caso, primero tenía que asegurarme de que la vpn no fuera la ruta predeterminada. La forma en que lo logrará depende del tipo de administrador de conexión que esté utilizando.
El proxy (tinyproxy) se ejecuta con su propio usuario, por lo que marco todos los paquetes que provienen de este usuario con el comando
iptables -t mangle -A OUTPUT -m owner --uid-owner 125 -j MARK --set-mark 2
donde 125 es el uid del usuario tinyproxy y 2 es un número arbitrario, para ser emparejado más tarde.
Luego indico al sistema de enrutamiento que use una tabla específica para enrutar todas las solicitudes marcadas con 2 .
ip rule add fwmark 2 table 3
De nuevo, el 3 es sólo un número arbitrario. Solo pida atención para elegir una mesa sin usar (solo vea si hay algo en la mesa con lo que elija con ip route list table 3 ).
Luego relleno la tabla 3 con mi ruta por defecto:
ip route add default dev ppp0 via proto static scope link metric 1024
El último paso fue hacer una regla de enmascaramiento, de la cual no entiendo completamente la necesidad:
iptables -t nat -A POSTROUTING -o ppp0 -j MASQUERADE
¡Et voilá!