Create quickly alternating clips in Premiere Pro
I would imagine that the music video you posted used manual edits to achieve that effect. However, there are a few automated beat detection utilities out there which you might like. One After Effects / Premiere plugin specifically dedicated to beat detection and music is Mamoworld's Beat Assistant. I haven't used the plugin (cost ~$40), but it should work with Premiere or After Effects. You can see a video tutorial and overview here.

For other ideas, Premiere Elements (but not Pro) does have a built-in beat detection feature. You could also investigate Trapcode's Sound Keys plugin, which might help you  more quickly place markers on beats by hand. If you can make cuts based on loudness of the music (as opposed to beats), you may be able to use the "Convert audio to keyframes" keyframe assistant.

Unfortunately, I'm not sure if beat detection tools will be able to easily / perfectly recognize an accelerando or tempo increase like you describe. You may be stuck doing some manual editing to at least identify the beats. Using Premiere's "Add clips to a sequence automatically" could speed up your workflow when it comes time to assemble the clips in place.