Isn't it just a matter of placing this on one of your category pages?
Code:
#
# Get products data for current category and store it in an array
#
$cat = intval($cat);
if ($cat) {
$category_data = func_query_first("SELECT categoryid_path FROM $sql_tbl[categories] USE INDEX (PRIMARY) WHERE categoryid='$cat'");
$result = func_query("SELECT categoryid FROM $sql_tbl[categories] USE INDEX (pam) WHERE categoryid_path LIKE '$category_data[categoryid_path]/%' AND avail='Y'");
...
Simply modify the SQL to query the table, but not limiting to $cat ....
then, ORDER BY RAND() and LIMIT 1 ...you should be set. LIMIT 3 if you use the random_products.tpl