Retina, 37 bytes
M!&`\G(.+?)(?!.*¶.*\1)
O$#`.+
$.&
G1`
Output is empty if no valid substring is found in A.
Try it online! (Slightly modified to run several test cases at once. The input format is actually linefeed separated, but test suites are easiest to write with one test case per line. The test framework turns the space into a linefeed before the actual code starts.)
Explanation
M!&`\G(.+?)(?!.*¶.*\1)
For each possible starting position in A, match the shortest substring which does not appear in B. The & is for overlapping matches, such that we actually try every starting position, even if a match is longer than one character. The \G ensures that we don't skip any positions - in particular, this way we have to stop at the linefeed, such that we don't get additional matches from B itself. The reason this doesn't mess things up is actually quite subtle: because if there's a starting position in A where we can't find any valid substring, then that's also a failure which will cause \G to stop checking any further positions. However, if (from the current starting position) all substrings appear in B, so will all substrings that start further right of the current position, so discarding those is not an issue (and actually improves performance).
Due to the M! configuration, all of these matches will be returned from the stage, joined with linefeeds.
O$#`.+
$.&
This sorts the lines of the previous result by length. This is done by matching the line with .+. Then $ activates a form of "sort-by", such that the match is substituted with $.& for determining sort order. The $.& itself replaces the match with its length. Finally, the # option tells Retina to sort numerically (otherwise, it would treat the resulting numbers as strings and sort them lexicographically).
G1`
Finally, we simply keep only first line, by using a grep stage with an empty regex (which always matches) and a limit of 1.