New build 2nd gen 737s were definately available with main deck cargo capablities as the 737-300QC's. LH got them straight from Boeing as did AQ.
Ha763, your statement above could be partly correct. But as far as I know Boeing delivered few newly built second generation aircrafts to Pemco World Air Services to be converted to the freighter version.
So probably the LH
/AQ aircraft you are refering to could have been from the aircraft conversion company.
This link will probably help http://freightersonline.com/plane.asp?a=11
I've tried doing a search to find if Boeing actually manufactured any second gen 737 cargo a/c, however I could'nt find any. Any info will be appreciated.