How to edit this non-static green screen and place a static image on it?

Morning all. Trying to edit an image onto footage of a phone with a green surface, but the internet is flooded with tutorials that only relate to the background. All anyone ever talks about is backgrounds!

I'm leaning towards Ultra Key>Alpha Channel>Export being the start of the path, but no amount of googling is getting me any further away from hundreds of pages of green screen background tutorials. Do I have to export to PS or AE and attempt a frame-by-frame alignment? I've only picked up Premiere in the last couple of days so I'm open to learning any solution to this. I know I could just pay a fiverr guy to do it because I've seen gigs just like this there, but I may be doing this a few times and it could be easy savings for me.

Example of clip in case I wasn't clear: http://www.videvo.net/video/smartphone-power-on/4239

EDIT: Been trying to do it with Premiere, but this sort of stuff is supposedly beyond it and it's best for removing green screen backgrounds. This is a job for After Effects, tutorial easily found with 'after effects screen replacement'.

Bump because this got 17/19 of its views in the 10 minutes it was most recent.

I don't know why people insist on putting green on these things, it doesn't help.

Your best bet is After Effect, you need to track the phone, use keylight to remove the green or just rotoscope it.