Se me ocurre que podrías monitorizar si tienes acceso a Internet con las acciones "Ping", "HTTP Get" o "Solicitud HTTP". Esta parte no debería ser complicada.
Para recuperar la conexión podrías intentar poner y quitar el "Modo Avión", y si eso no funciona puedes usar la acción "Reiniciar" como recurso extremo. Para estas cosas necesitarás root y/o dar los permisos adecuados siguiendo las instrucciones de la documentación de Tasker.