The short answer: Yes
Yes, at Administer > Communications > FROM Email Addresses, you can add any number of email addresses, and they're not restricted to any particular domain.
-- that technically answers your question, which was specifically about CiviMail (the bulk mailing component of CiviCRM). You can also specify custom "From" email addresses for Scheduled Reminders.
The longer answer: Yes, and you may need multisite
However, for transactional/system emails (automated emails such as subscribe and unsubscribe confirmations), in a normal, single-site CiviCRM instance you can have just one "From" address. This is set at Administer > Communications > Organization Address and Contact Info.
I suspect the best solution for your use case may be CiviCRM in multi-site mode. This way you can have different transactional email addresses for each domain. So, for example, when a contact subscribes to a mailing list on your c3 site, the confirmation message will come from the c3 domain.
In multi-site, contacts can be shared between your two domains (but they don't have to be). This sounds like what you want, but it may lead to behavior that could be surprising in some cases. For example, when a contact clicks an "opt-out" link on one of your c3 emails (not just unsubscribing from the current list, but from all of your email communications), their opt-out will apply to your c4 mailings too.