... collisions are still possible in this second level
For each slot of the first-level hash table (which contains more than 1 keys), we will need to decide a hash-function. Since we want perfect-hashing, we want this function to give no collision. Theorem 11.9 (quoted below) guides us that it is in-fact possible to find such a function in a universal-class, with probability atleast 1/2 (meaning, atleast half of them are collision-free for this slot's keys). So, with a very few random trials, we can hope to succeed in finding such function. With each trial, we need to check all keys in that slot to know if this is the one which works. And this task needs to be repeated for all slots of first-level table.
So, collisions are possible if we simply pick this second-level hash function randomly, without checking/ensuring as above. A collision-free function can be found with a one-time exercise (since keys are static) as above.
... so to truly have no collisions in this 2nd level, one may need to try a few hash functions in this level for each value of j.
True, for each value of j. Each slot contains different set of keys, and so the non-collision function needs to be worked out separately for each slot's set of keys.
Is it fair to assume that a simple sequence of random "try and error" (i.i.d sampling) of hash functions (in this 2nd level) is "as good as it gets" at least for this perfect hashing design?
Since our aim is no collisions at the second-level, I think the individual sets of keys in each slot does require the trial-error, because the hash functions outcome really depends upon the input keys. (I have not yet checked the Fredman's (et al.) paper you referenced).
Theorem 11.9, quoted (CLRS): "If we store $n$ keys in a hash table of size $m=n^2$ using a hash function $h$ randomly chosen from a universal class of hash functions, then the probability of there being any collisions is less than 1/2."