Picking two different random numbers fast

Sometimes one requires random numbers with the condition that they are unique.

The classic algorithm is to keep looping until you hit the different numbers by chance, some pseudo code:

 minval = 0 ;
 maxval = 4 ; // random max will be one less than maxval

 val1 = random( minval , maxval ) ;
 val2 = random( minval , maxval ) ;

 while( val1 == val2 ) {

  val2 = random( minval , maxval ) ;

 }

I have a time critical and memory limited program and was wondering if there are any algorithms that avoid the continuous loop brute force method without using extra memory like a look up table.

Probably a simple solution but it's a late and tired evening here.

Any tips?