Getting Random Sample from large database MYSQL (No Auto Inc Field)
This may sound rather evil but you might find this interesting

Suppose your table looked like this

CREATE TABLE massiveTable
(
    PK VARCHAR(50) NOT NULL,
    ... Other Fields ....
    PRIMARY KEY (PK)
) ENGINE=MyISAM;


Step 01 : Create a Empty Copy of the Table and another for Keys

CREATE TABLE randomKeys SELECT PK FROM massiveTable WHERE 1=2;
CREATE TABLE randomTable LIKE massiveTable;


Step 02 : Iteratively load every fifth key

SET @x = 0;
INSERT INTO randomKeys
SELECT PK FROM
(SELECT PK,(@x:=@x+1) num FROM massiveTable) A
WHERE MOD(num,5)=0;


Step 03 : Create the Random Temp Table

ALTER TABLE randomTable DISABLE KEYS;
INSERT INTO randomTable
SELECT B.* FROM randomKeys A LEFT JOIN randomTable B USING (PK);
ALTER TABLE randomTable ENABLE KEYS;


Step 04 : There is no Step 04. That's it !!! No stored procedure needed.

CAVEAT : I cannot make any promises on the running time or query processing.

Give it a Try !!!