We've been changing diapers on floors since each of my kids were able to roll over in any direction, as both of them prefer to move every way they can to lying still. One's still under 2, so he's the one who's difficult to handle when he's standing.
We have a fold-up changing mat (Skip Hop brand I think) that we carry with us and lay it down on the floor of a restroom, a corner in any other room, on a public hang-down changing table in a "family" restroom. The folding mat has a place for the kid to lie on top of, a pocket to wipes and one to hold diapers.
A good way to keep them from moving around is keep their attention on your face, distracted from everything else... sing to them playfully, create a little game with their nose or their ears, give them mouth-things to play with. Toddlers don't have complex thoughts, so talking to them needs to as much like personal play as you can get it. I sometimes start singing louder to bring their attention back, and then change words in a song to include their name, or some silly rhyme, or snag their ear and tickle it.
Any activity that grabs and keeps and re-grabs their attention is my sole surviving tool in the diaper-changing-toolbox.