Generating random strings
A couple of points to consider:


Calling your function shuffle instead of random would be a better name since that's really what it's doing.
The extra intermediate tables aren't really necessary to perform the shuffle. A single table is enough and you can perform the shuffle in-place right on that table.
Consider a better separation between the process of shuffling and how the input is stored. For example, if you have your shuffle function take a table instead then that function can be reused on any kind of data and not just strings.
I would do away with the Hungarian notation and just drop the type prefix on the variable names. Remember Lua variables themselves doesn't have a type. If you later change what that variable refers to then the Hungarian notation becomes misleading.


So I would refactor your original code into two functions. Here's one possibility:

function shuffle(self)
  if type(self) ~= 'table' then return nil end

  for i = #self, 2, -1 do
    local randi = math.random(i)
    self[i], self[randi] = self[randi], self[i]
  end
  return self
end

function shuffle_words(str)
  local strtable = {}
  for each in str:gmatch("%a+") do
    table.insert(strtable, each)
  end
  return table.concat(shuffle(strtable), ' ')
end