Are licensed "builders" required to pull permits
Can a licensed contractor perform work, that requires a permit, without a permit?

If the work requires a permit - that is a City / State Ordinance [aka LAW]- the answer is while the contractor could perform the work - it is a violation of the Ordinance. 
It is possible that the contractor might have it in fine print where it requires you to get the permits. They do the work "assuming" you have the permit or are in process. You can check to see if they really are licensed - I doubt a licensed contractor would do anything with out the permits.

This presents two problems:


If you are found out to have done this work with out a permit you
are probably going to be required to undo the work. 
The other issue you have is in selling the property - changes to the
property can be looked into and a buyer or a buyers inspector can
check for permits on the property.

a: In this case you would need to get it permitted in order to sell the property, which winds you back to the possibility of undoing the work at your expense of course. 


The Contractor probably requires you to get permitting - somewhere in the fine print so they can cover themselves. In the end you will be out the money you pay to the contractor and possibly more to have it all undone.

Get a contractor who will get the required permits, ask for the variance as it is an existing basement - you just might get it unless you are intending to make the ceiling height lower in your remodel.
 I assume you are going to put in rooms of some sort or a entertainment space.

if you are turned down , you are turned down; permitting is not expensive - undoing completed work is.