You CAN key the pivot point.
Kinda hokey, but it can be done. I'll try to describe it:
1) First, open the cube's attribute editor. Assuming your cube is named pCube1, click the pCube1 tab. Open the Pivots folder and check "Display Rotate Pivot." You can also open the World Space folder.
2) Move your pivot point to the edge of the cube where you want the first rotation to happen.
3) Open Window > General Editors > Channel Control. Move the following from Unkeyable to Keyable:
These will appear in your Channel Box.
4) Go ahead and key the first rotation of the cube at the edge where your pivot point currently is. When it rotates 90 degrees and it comes to the point where it will need to then change pivot location in order to roll on the next edge, go forward one frame and in the World Space folder of your cube, change the World Rotate Pivot X, Y, or Z. In my case, my cube was 16 units large, so I moved it 16 units in the X direction. You'll notice a few of the channels that you added change to indicate this movement of the pivot. Key them in the Channel Box. Now, go back one frame, put the pivot back to it's original position, and key those same channels again.
5)Step and repeat.
Image - http://www.mtmckinley.net/SimplyMaya/pivot.jpg
Video - http://www.mtmckinley.net/SimplyMaya/cubeRotate.avi
Maya 5.0 file - http://www.mtmckinley.net/SimplyMaya/rotate.mb