Can I license an idea to a company without having it patented?

Ummm ... it comes down to the basic rules of licensing ... how to detect cheating (on both sides) and what can be done to enforce the contract. Note that NDAs usually fall into trade secrets legislation and is completely separate from the licensing of IP (which can be based around copyright and right to access secret information). The trick with licensing is coming up with the right combination of licenseable material (if include patents need indemnities) and how you envisage the product to be developed to make sure the mutual advantages are retained ... see the Sun Java API v google clean-room cloning as counter-examples.