How to check if an entity is referenced before deleting? Is there a module or a way to use Rules to make sure that a parent node isn't referenced by a child node before deleting the parent? 

In my case the children require a parent to be created. However if the parent gets deleted, the children all get screwed up.
(Entity)Reference Field Synchronization module should be able to help:

Having 2 Entity reference fields pointing back at eachothers entities, they can be set to be updated so that if an entity A with field 1 references to an entity B with field 2, entity B automatically points to entity A.
This is very helpful when you need to be able to reference from any entity, and not just be able to perform back reference queries (as provided by Entity reference).

Just add an synchronized reference field to a parent, and on delete test if it has values or not.
Also, see this feature request in Entity reference issue queue.