If caching is enabled at the .htaccess level, there’s not much you can do through a plugin to intercept that traffic. Instead, you should work out a set of recommended .htaccess rules that work with both W3TC and your plugin to either allow traffic through or return cached content.
Perhaps, auto-generate a list of user agents you want to send custom headers for and use that list—through .htaccess—to allow certain traffic to bypass the cache.