I think that users in folders is going to be tough. There is not much abstraction in the code wrt URLs, a lot is done by convention and changing the behavior would mean changing stuff all around the place.
As John mention, wildcard DNS is the best option. I got it running on a bluehost account in the past without issues. It was just required to contact their support directly to get the wildcard dns setup, it was not possible to configure it directly from the cpanel.
Let us know how it works,
-Laurent