MATL, 22 19 bytes
tZ"ibpyn&Z@(TT35&Ya
Thanks @LuisMendo for saving 3 byesbytes, so now it has the same bytecount as @flawr's answer, but sufficiently different to post anyway. High-level agorithm overview:
Z" % Create n x m matrix of spaces
( % Index into this matrix:
i % The alphabet vermicelli (explicit input)
&Z@ % at a random locations (randperm), which are
yn % length(S) numbers, ranging
t bp % from 1 to n*m
TT35&Ya % And finally add a border