Echando un vistazo al CORDE encuentro un par de casos en los que podríamos estar ante el antecesor del "venga" como muletilla sin significado. Son los siguientes:
[...] la oradora abrió la mano izquierda, haciendo ademán de escribir en ella con una tagarnina–: "Decreto yo, el pueblo soberano, en uso de mis derechos individuales, que todos los generales, gobernadores, ministros y gente gorda salgan del sitio que ocupan y se lo dejen a otros que nombraré yo del modo que me dé la realísima gana. He dicho."
–¡Bien, bien!
–¡Venga de ahí!
Emilia Pardo Bazán, "La Tribuna", 1883 (España)
–Entonces... ¡venga otro trago! –exclamó el molinero, sentándose.
–¡Venga de ahí! –repuso el alcalde, alargándole el vaso lleno.
Pedro Antonio de Alarcón, "El sombrero de tres picos", 1874 (España)
En este último caso podemos ver que el primer "venga [otro trago]" equivaldría al primer ejemplo del café que pusiste, pero la respuesta "venga [de ahí]" equivaldría más bien al "venga" como "vale, de acuerdo".
De hecho, yo mismo he usado expresión como "venga ahí" usada para dar ánimos. Es muy probable que esta sea la expresión que se acortara y originara el actual "¡venga!" como interjección.
Te pongo un ejemplo más, en el que aparece "venga de ahí" con el sentido de "vale, adelante":
–[...] Voy a contarle a usted una cosa muy curiosa que me ocurrió hace poco.
Afiné mis cinco sentidos ante las palabras de este hombre, cuya naturalidad en el trato demostraba bien a las claras la certeza de sus explicaciones.
–Venga de ahí –contesté yo, deseoso de oírle.
Julio Escobar, "Itinerarios por las cocinas y las bodegas de Castilla", 1965 (España)
Una buena pregunta ahora podría ser ¿a qué se refieren con "ahí"?