Can I use another cloud storage for my device besides iCloud?

I'm not familiar with Verizon storage but you can use Google Drive and/or Google Photos.

See: https://support.google.com/drive/answer/2424384?co=GENIE.Platform%3DiOS&hl=en

and

https://support.google.com/photos/answer/6220402?co=GENIE.Platform%3DiOS&hl=en

Another option is Microsoft OneDrive.

Note that they will not work for some things such as iCloud Backup.

Two things to try to stop the message:

Free up some space if you can: Manage your iCloud storage - Apple Support

Turn off iCloud Backup if you don't want to use it: Settings > [username] > iCloud > iCloud Backup > iCloud Backup - off.