When I say hexahedral mesh, I mean generate hexahedron to mesh a volume (see http://www.robertschneiders.de/papers/vki.pdf). ParaView can mesh surface, not sure if it can mesh the volume. I will check it.
As far as I know, generating tetrahedral mesh is way easier than generating hexahedral mesh. That is one of the reasons free hexahedral mesh generator is rare (a few good ones can be found in Eric's link).
I'm also looking forward an open source hexahedral mesh generator. The only one I found is the blockMesh utility in OpenFOAM. Have you found anything else?