If you have a Google account you can choose to have everything such as contacts and apps backed up and associated with your account so the next time you get a new phone, once to stick your Google account into it, it'll automatically restore your contacts and apps.
As for videos and pictures you should have an app on your phone such as OneDrive, Google drive or Dropbox that continuously back up your stuff in the background. You can choose WiFi only back up or if you have a nice unlimited plan choose mobile data also.
You can also of course plug your phone into a laptop and backup everything to that or external hard drive.
That should be everything you need.
There are various applications available in the app store for the backup purpose, so you might have to use multiple apps. Latest Android phones are coming up with free drive storage upto some extend like Samsung provide 15gb storage for all your stuff.