The simplest solution is to generate a random point within the rectangle and reject it if it lies in the polygon. You would repeat the process until you got a valid point. This same algorithm is used to uniformly distribute points over an area or volume, except points that are considered outliers are rejected. This type of sampling is known as rejection sampling, if you want to research it further.
The way I would do the polygon test is to test the point against the 4 edges individually. Imagine that all the lines extend out to infinity in both directions. Any point on the 2d plane belongs to one of the two partitions created by a single infinite line. For example:
(0, 2) (4, 2)
The two points
(0, 2) and
(4, 2) form the line at y = 2. Point A is considered "above" the line, while point B is considered "below" the line.
Now extend the idea to 4 of these lines. If a point tests in a specific way for all 4 lines, the point has to be in the polygon. This is the same logic used when testing for point containment in an AABB, just simplified where all the lines are parallel to the X or Y axes, making the comparison much simpler.
The way this is calculated on a computer is actually very straightforward, this StackOverflow answer provides a function that takes 3 points - 2 that form a line and one to test.
If you use the same function as on the SO answer, you'll want the left edge of the polygon to return false, the right edge to return true, the top edge to return false, and the bottom edge to return true for the point to be considered contained.
The test requires, in the worst case, 20 subtractions, 8 multiplications, and 4 comparisons. Even on a low-end smartphone, that's nothing. Even having to test several points per frame, it won't make a dent in performance.
The benefit of this kind of sampling over your suggested moving of the point is that any simple algorithm for moving the point will skew your distribution to be more dense around the polygon. Rejection sampling keeps the same distribution, it just cuts out anything that doesn't belong.