Your paying for a webhosting and it charges more for the cgi-bin? Or do you have a cgi-bin and the charge to be able to run cgi programs in any directory?
Personally, If I were dealing with a webhosting that charged extra for cgi-bin access, I would look somewhere else.
As was said, there are some options, but there are also alot of webhosting that do NOT charge for cgi-bin access.