While looking into this question, I found a list of certificated air carriers on the US Department of Transportation website (there's a list of commuter air carriers too). But, the list doesn't say if each one operates under part 121 or part 135, which the DoT seems to consider an FAA question anyway:
As noted above, the economic authority issued to air carriers by the Department is separate from the safety authority (commonly referred to as Part 135 or Part 121 Operations Specifications) granted to them by the Federal Aviation Administration (FAA). For safety authority application procedures and related questions, air carriers should contact the appropriate FAA flight standard district office based upon the geographical location of the air carrier
The FAA site has a lot of information about part 121 operations, but at least as far as I could see there's no list of 121 or 135 carriers anywhere on their site.
Is there a list somewhere of current part 121 and/or 135 operators?