How do I feasibly generate a random sample from an ndimensional ell_p ball? Specifically, I'm interested in p=1 and large n. I'm looking for descriptions analogous to the statement for p=2: Take n standard gaussian random variables and normalize.

For arbitrary p, this paper does exactly what you want. Specifically, pick $X_1,\ldots,X_n$ independently with density proportional to $\exp(x^p)$, and $Y$ an independent exponential random variable with mean 1. Then the random vector $$\frac{(X_1,\ldots,X_n)}{(Y+\sum X_i^p)^{1/p}}$$ is uniformly distributed in the unit ball of $\ell_p^n$. The paper also shows how to generate certain other distributions on the $\ell_p^n$ ball by modifying the distribution of $Y$. 


I'll assume that you're looking for a uniformly chosen random point in the ball, since you didn't state otherwise. For p=1, you're asking for a uniform random point in the cross polytope in n dimensions. That is the set $ C_n = \{ x_1, x_2, \ldots, x_n \in \mathbb{R} : x_1 + \cdots + x_n \le 1 \}. $ By symmetry, it suffices to pick a random point $(X_1, \ldots, X_n)$ from the simplex $ S_n = \{ x_1, x_2, \ldots, x_n \in \mathbb{R}^+ : x_1 + \cdots + x_n \le 1 \}$ and then flip $n$ independent coins to attach signs to the $x_i$. From Devroye's book Nonuniform random variable generation (freely available on the web at the link above, see p. 207 near the beginning of Chapter 5), we can pick a point in the simplex uniformly at random by the following procedure:
So do this to pick the absolute values of the coordinates of your points; attach signs chosen uniformly at random, and you're done. This of course relies on the special structure of balls in $\ell^1$; I don't know how to generalize it to arbitrary $p$. 

