I'd like to sample a vector $\mathbf{x}\in\mathbb{R}^k$ such that $\frac{\mathbf{x_i}}{|\mathbf{x}|}\geq c$ for all $i$ where $c \in [0,\frac{1}{\sqrt{k}}]$. Is this possible? How can this be done?
So far, what I've been doing is randomly sampling a uniform distribution with a small interval and accepting the sample when the constraint is met.
Let $z^i$ be the vector whose coordinates are all equal to $c$, except for the $i^{th}$ coordinate which is $\sqrt{1-(k-1)c^2}$. Note that $|z^i|=1$, and each coordinate of $z^i$ is at least $c$. Therefore, $z^i$ is a vector which fulfills your constraints.
Furthermore, any convex combination of the vectors $z^i$ will fulfill your constraints. To see this, note that if $\lambda_i$ is a list of positive numbers summing to one, and $z=\sum \lambda_i z^i$, then using the triangle inequality, $$ z_j=\sum_i \lambda_iz^i_j\ge c\sum \lambda_i |z^i|=c\sum |\lambda_iz^i|\ge c\left|\sum_i \lambda_i z^i\right|=c|z| $$
Therefore, one valid method is to randomly choose $k$ positive numbers $\lambda_1,\dots,\lambda_k$ summing to $1$, and let ${\bf x}=\sum_i \lambda_i z_i$. To do this, see simplex sampling.
To add a little more variety, you instead let ${\bf x}=R\sum_i \lambda_i z_i$, where $R$ is any positive random scalar. As long as the support of $R$ is $(0,\infty)$, then the support of this sampling method is the set of all admissible vectors.