How to clear Stock Browser cache when browser isn't installed?
As a side-effect of clearing all caches of all apps: boot into recovery-mode, and select "wipe cache". That wipes caches of all apps, but keeps your apps and data themselves intact.

If you have usb-debugging activated and adb available to use, there's a command doing the very same:

fastboot erase cache


This comes in handy especially for devices where you cannot access the recovery-mode.

Hint: you might be tempted to suggest adb shell pm clear com.android.browser for the very same purpose, restricting the purge to the specific app. Note that this is not only clearing the cache, but all the app's data as well. And it requires "elevated permissions" (i.e. root) to be executed – which is probably why it returned "failed" when you tried. The full command would then read:

adb shell su -c "pm clear com.android.browser"