hace un tiempo me enfrente al mismo problema, al final desistí y no lo avancé pero
hice esto con javascript, en esa época mi manejo de js era super básico y fué lo mejor que pude hacer. Supongo que se lo puede mejorar usando alguna librería para que sea compatible con todos los navegadores.
Espero te sea útil aunque sea como punto de partida.
Lo peor es que no solo los campos input:file son un horror de personalizar sino que la nueva especificación html5 incorpora nuevos elementos de formulario (sliders, calendars, etc) que por su nivel de complejidad para tratarlos con css uno prefiere seguir usando los componentes de jquery ui por ejemplo o similar. Me llama la atención como descuidan tanto este tema.