Tal vez con algunos agregados.
Supongo que será posible mejorar mi ejemplo, por ejemplo en vez del div aplicarlo a <legend>.
Trate aplicar el pseudoelemento :before directamente al input, pero no lo logre.
El ejemplo:
http://jsfiddle.net/c2am/mcgct/97/embedded/result/
Saludos