Is there any simple method to generate random numbers, which follow super-Gaussian distribution?
$$f(x,y)=A\exp \left(-\left({\frac {(x-x_{o})^{2}}{2\sigma _{X}^{2}}}+{\frac {(y-y_{o})^{2}}{2\sigma _{Y}^{2}}}\right)^{P}\right)$$
One idea was rejection sampling, but drawing a bounding box would cut off the tails.
This'll be for the case $P>1$.
With a slight change in notation your density $f$ is proportional to $\exp(-\phi^P(x, y))$ where $\phi(x, y) = (x - m_X)^2/{2\sigma_X^2} + (y - m_Y)^2/2\sigma_Y^2$. You have a bivariate Gaussian for $P=1$.
First the easy part. If we knew there to be a constant $a$ for which $a \exp(-\phi(x, y))/\exp(-\phi^P(x)) \geq 1$ for all $x$ and $y$, a simple acceptance-rejection procedure would be:
There is such an $a$. For $P > 1$ the smallest value of $\exp(-u)/\exp(u^P)$ for $u \geq 0$ occurs at $u_0 = P^{-1/(P -1)}$, so we can choose $a = \exp(u_0 - u_0^P)$ as the rejection constant.
I doubt this generator will have uniform performance as $P \rightarrow \infty$, you typically have to do a bit more work for that, but maybe this is a start.