Shove is an attack
There's no general rule saying that all attacks must use an attack roll
This trips up a lot of people (and for good reason) but the statement you quote from the PHB does not define attack as anything that involves an attack roll.
If there’s ever any question whether something you’re doing counts as an attack, the rule is simple: if you’re making an attack roll, you’re making an attack. (PHB 194)
Reading it carefully, this rule says that if you are making an attack roll then you are making an attack, but it does not say that if you aren't making an attack roll you aren't making an attack. To use a hopefully clearer real-world example of this logic: the statement "if you're under water you're wet" does not mean that it is true that "if you're not under water you're not wet."1 In fact, it says nothing at all about your moisture status if you aren't under water.
To put it another way in game terms, all things that involve attack rolls are attacks, but this statement says nothing about cases where you aren't making an attack roll.
So how can one tell if something that isn't using an attack roll is an attack or not? Well, the first thing to do is check to see if the wording calls it an attack or not.
Shove is an attack because it says it is an attack
The rules for shoving say:
Using the Attack action, you can make a special melee attack to shove a creature, either to knock it prone or push it away from you. If you're able to make multiple attacks with the Attack action, this attack replaces one of them. (PHB 195)
Twice in this rule it calls a shove an attack. This simply means that the rules are telling you that this is an attack. And it doesn't even contradict any general rules (as shown above), though it does make it a bit of an oddball. But being an oddball is no reason to doubt the rules when it tells clearly that this is an attack.2
1 Credit to @Medix for the suggestion in a comment under another answer.
2 And if you needed even more assurance (and you give any credence to designer interpretations), Jeremy Crawford has also made an unofficial ruling to the same effect here:
An attack involves an attack roll or doing something that the rules call an attack, like grappling or shoving.
And here (for the near-identical case of the grapple):
The grapple option in the Player's Handbook is an attack, but it uses an ability check in place of an attack roll.