Add ability to add bundles to an entity that does not currently have bundles? If you have a custom entity that does not create bundles, is it possible to modify it to allow new bundles to be created?
Possible yes, although not trivial. Not having a bundle means internally, Drupal exposes a default bundle that has the same name as the entity type. So the by far easiest approach would be to create a bundle entity type, create a default bundle with the same id (possibly only in the update path for existing sites) and then allow to create additional ones.

What's hard is changing the bundle of an entity type, that's not officially supported. file_entity does it for the file entity type, you can have a look at its entity class and the methods it overrides the detect the file type and based on that, sets the bundle.