Is it possible to add a custom field of type checkbox, default checked, and have it make all EXISTING records be checked?

Defaulting it to checked only applies to a new record and not existing records. You could use a csv import or a mass update to update the existing records for the new field.