Que yo sepa todos los navegadores stock de Android conservan el historial para siempre. Hasta que la caché se limpie manualmente o se limpie a causa de una actualización OTA - ya que estoy bastante seguro de que las actualizaciones limpian la caché antes de arrancar - Aún así, estoy bastante seguro de que la caché del navegador no se toca en ese proceso.
Estoy bastante seguro de que no tienes nada de qué preocuparte en cuanto a perder la historia.
Si estás ejecutando la versión 4.0.x (creo que es exclusiva de esa versión, podrías comprobarlo), puedes obtener el navegador Chrome Beta, que mantiene tu historial sincronizado con tu cuenta de Google, junto con tus marcadores y, por supuesto, el historial de cualquier otra máquina en la que ejecutes Chrome.
Bastante bien.