Based on the comment by Ryan Cory-Wright, you could formulate it like this.
Verify convexity of the domain $\{x \in X : g(x) \le 0\}$
Solve the following problem, and check the optimal value.
\begin{align}
\max\qquad& g\left(\lambda x + (1-\lambda) y\right) && \small\textrm{(maximize constraint violation of convex combination)}\\
\text{s.t.}\qquad& g(x) \le 0 && \textrm{($x$ is feasible)}\\
& g(y) \le 0 && \textrm{($y$ is feasible)}\\
& 0 \le \lambda \le 1 && \textrm{(define convex combination)}\\
& x, y \in X && \textrm{(definitions $x$ and $y$)}\\
\end{align}
If the optimal value is (strictly) positive, then the set is not convex, as $x$ and $y$ are both in the set, while their convex combination $\lambda x + (1-\lambda) y$ is not. If the optimal value is non-positive, then the set is convex.
Verify convexity of $f$ on the domain $\{x \in X : g(x) \le 0\}$
Solve the following problem, and check the optimal value.
\begin{align}
\max\qquad& \small f(\lambda x + (1-\lambda) y) - \left(\lambda f(x) - (1-\lambda) f(y)\right) && \small\textrm{(maximize violation of convex combination)}\\
\text{s.t.}\qquad& g(x) \le 0 && \textrm{($x$ is feasible)}\\
& g(y) \le 0 && \textrm{($y$ is feasible)}\\
& 0 \le \lambda \le 1 && \textrm{(define convex combination)}\\
& x, y \in X && \textrm{(definitions $x$ and $y$)}\\
\end{align}
If the optimal value is (strictly) positive, then there exists a convex combination such that $f(\lambda x + (1-\lambda) y) > \lambda f(x) + (1-\lambda) f(y)$, which violates convexity. If the optimal value is non-positive, $f$ is convex.
Solving the above problems
As you already mention, solving the above problems could be very difficult, even if $f$ and $g$ are actually convex. Things can become even more difficult if the functions are 'weird'. For example,
$$g(x) = \begin{cases}\textrm{0 if $x \in \mathbb{Q}^n$}\\\textrm{1 if $x \notin \mathbb{Q}^n$}\end{cases}$$ seems very problematic!