Is anyone aware of a hosting company that offers, cgi-bin, perl, asp, php, subdomains, and access databases?

I believe Prevo.net supports all of this.

Try going to a hosting directory that has all of those features as options for a host search, then all hosts who offer those features will come up.
If that makes sense.. :)

Yes, try http://hostsearch.com/.