How do I add the With Contact information to the email that gets sent to activity assignees?
The template to edit is the one called "Cases - Send Copy of an Activity" under Administer - CiviMail- Message templates and then click the System Workflow tab. The name is historical - it isn't just for cases.

But it seems like it's not currently possible to get the With Contact information since even the activity id is not available in the template. There is minimal data to work with.

You could do this by customizing CRM_Case_BAO_Case::sendActivityCopy() to include more information. I could see that being useful as a core improvement, to at least include the activity id and related contact ids.

Note that it's possible to have multiple With Contact's on an activity, so if there's more than one you'd need to handle that.