Building custom entities, but using existing modules? I've noticed a lot of useful modules already created such as workflow, ACL, diff, and more. But these only seem to work with "content types". In our project, we have decided that "content types" aren't really well suited for what we need (Entities make more since). Very complex relationships must be modeled. Our entities are just that, entities, not content. 

The problem is that when building an entity using hook_schema() and hook_entity_info(), these entities are not available to be used with different modules such as workflow. Is there any way to make them available? Or will we have to code similar workflow functionality by hand?

Workflow does exactly what we need, except only on content types. We need it to work on entities as well.
Especially in Drupal core, Nodes are still something like a Super-Entity with a number of features only supported by them, like revisions and the whole node_access thing. The entity.module tries to implement these features generically for all entities, I'm not sure if everything is covered yet.

Many modules only support nodes both due to these missing features (You can't configure ACL's or workflows if there is no way to limit access in the API, diffing is pointless without revisions) and historical reasons (all of your listed modules are ports initially Drupal 6 versions or even older and have been ported to Drupal 7). The whole concept of entities represents a major shift in Drupal and not all modules have made that step (yet).

I guess that's one of the reasons why e.g. Commerce uses Nodes as the default way to display products.

Work is ongoing in Drupal 8 to unify these features and provide them for all kinds of entities.

This is not really an answer to your question, more an explanation of the status quo. As Alex already mentioned, many of those modules are working on supporting entities or an entity-aware successor is being worked on, like http://drupal.org/project/state_machine.