Yep, "push her over" and "push her off" both sound fine to me.
As nouns, though, "push-over" and "push-off" are very different. "A push-over" is someone who's not very strong willed and others can take advantage of, and a "push-off" is what you do when you push against something to move yourself in the other direction.
Its pretty clear either way but push her over has more ambiguity For instance if she was not at the edge she might just land on the grass.if you push her over. You could use this to fool the reader who would probably assume you meant off the cliff. Then later reveal that she did not go off the cliff.
The sentence is a charming English grammatical result when two entirely separate idioms are wed to convey the very same result. From a cliff's point of view, all the things of the world go over it and follow a course downwards provided that they follow the rule of gravity. From a standpoint of something that is on, in the idiom it is there until it is taken, dragged, pulled, or pushed to the off position. Yes, there are exceptions. However, dear historical speech results in idioms are something over the cliff and something off the fence.