Rotatating a character

The game you've linked in your question doesn't use a regular physics engine; it probably fakes the physical rules it needs to work, including collision detection and gravity. Trying to reproduce exactly the same behaviour would be a really hard work, but if you just want the "flopping" walk style, the script below can do the job. Just create a cube and attach this script to it. If you want the flop sound, add an AudioSource and assign an appropriate sound to it (footstep4 from the FPS Tutorial is fine).
The idea is to flop the block using RotateAround, like @EliDavis suggested. When some movement key is pressed, the routine Flop defines around which point and axis the block will rotate, then does a 90 degrees rotation during the time defined by speed. To avoid accumulated errors, the routine AlignBlock is called prior moving. This routine forces orientation alignment to the axes by rounding the eulerAngles to multiples of 90 degrees. It also forces the position alignment to multiples of the block size (defined by size) thus the block will always walk in a grid with size spacing.
If the block has no rigidbody, it will be a really nice guy, flopping precisely over the grid positions - but will not be constrained by collisions nor be affected by gravity. If you add a rigidbody, it will collide and fall, but the flopping action will become somewhat weird (it sometimes stops for a while before ending the 90 degrees rotation). Anyway, the AlignBlock routine will always bring it back to the right position before moving.
NOTE: if a rigidbody is added, AlignBlock ignores Y to not interfere with gravity.

var speed: float = 4; // flops per second var size: float = 1; // block size var flopping = false;

function Update(){

 var move = Vector2(Input.GetAxis("Horizontal"), Input.GetAxis("Vertical"));
 if (move.magnitude > 0.2) Flop(move);

}

function Flop(movDir: Vector2){

 var pivot: Vector3;
 var axis: Vector3;
 var fDir: float;
 
 if (flopping) return; // ignore other commands while flopping
 flopping = true; // signals it's flopping
 if (movDir.y > 0){ // move forward?
     axis = Vector3.right; // will rotate around x axis
     pivot = Vector3(0,-1,1); // defines point around which rotate
     fDir = 1; // angle of rotation positive 
 }
 else
 if (movDir.y < 0){
     axis = Vector3.right;
     pivot = Vector3(0,-1,-1);
     fDir = -1;
 }
 else
 if (movDir.x < 0){
     axis = Vector3.forward;
     pivot = Vector3(-1,-1,0);
     fDir = 1;
 }
 else
 if (movDir.x > 0){
     axis = Vector3.forward;
     pivot = Vector3(1,-1,0);
     fDir = -1;
 }
 AlignBlock(); // aligns block to grid before flopping
 // calculates the point around which the block will flop
 pivot = transform.position + (pivot * size / 2);
 var a: float = 0;
 while (a < 1){
     var dt = Time.deltaTime * speed;
     a += dt;
     // rotates +/- 90 degrees around axis 
     transform.RotateAround(pivot, axis, fDir*90*dt);
     yield;
 }
 if (audio) audio.Play(); // makes the flop sound 
 flopping = false;

}

private function AlignBlock(){

 var angles = transform.eulerAngles;
 // forces euler angles to be multiples of 90
 angles.x = 90 * Mathf.RoundToInt(angles.x / 90);
 angles.y = 90 * Mathf.RoundToInt(angles.y / 90);
 angles.z = 90 * Mathf.RoundToInt(angles.z / 90);
 transform.eulerAngles = angles;
 var pos = transform.position;
 // forces x and z to be in a grid 
 pos.x = size * Mathf.RoundToInt(pos.x / size);
 pos.z = size * Mathf.RoundToInt(pos.z / size);    
 // doesn't modify y if the block has a rigidbody
 if (!rigidbody) pos.y = size * Mathf.RoundToInt(pos.y / size);
 transform.position = pos; // comment out this line to ignore grid positioning

}