Allocate space in Cassandra
Simply put, nodetool cleanup will remove data from a node that it is no longer responsible for.  This can happen when adding new nodes to a cluster, as they assume token ranges once held by other nodes.  Once the data is streamed to the new node(s), it isn't automatically removed from the pre-existing nodes.  This is intentional, in that if a new node fails to bootstrap no data is lost.

Running a cleanup will indeed remove potentially orphaned replicas.  Normally, it is a good idea to ensure that repairs have been successfully completing prior to running nodetool cleanup.

In this case, as repair has never been run, I can't imagine that the application users really care about data consistency at this point.  But one thing to try, might be to run cleanup on one node to get some space back, followed by repair on the same node.  Work your way through the cluster running repair/cleanup (in that order) on each.  That should minimize the risk of data loss, while allowing for restoration of some semblance of consistency.