Are there any non-distance based clustering algorithms? It seems that for K-means and other related algorithms, clustering is based off calculating distance between points. Is there one that works without it?
 A: One example of such a method are Finite Mixture Models (e.g. here or here) used for clustering. In FMM you consider the distribution ($f$) of your variable $X$ as a mixture of $K$ distributions ($f_1,...,f_k$):
$$f(x, \vartheta) = \sum^K_{k=1} \pi_k f_k(x, \vartheta_k)$$
where $\vartheta$ is a vector of parameters $\vartheta = (\pi', \vartheta_1', ..., \vartheta_k')'$ and $\pi_k$ is a proportion of $k$'th distribution in the mixture and $\vartheta_k$ is a parameter (or parameters) of $f_k$ distribution.
A specific case for discrete data is Latent Class Analysis (e.g. Vermunt and Magidson, 2003) defined as:
$$P(x, k) = P(k) P(x|k)$$
where $P(k)$ is probability of observing latent class $k$ (i.e. $\pi_k$), $P(x)$ is probability of observing an $x$ value and $P(x|k)$ is probability of $x$ being in class $k$.
Usually for both FMM and LCA EM algorithm is used for estimation, but Bayesian approach is also possible, but a little bit more demanding because of problems such as model identification and label switching (e.g. Xi'an's blog).
So there is no distance measure but rather a statistical model defining the structure (distribution) of your data. Because of that other name of this method is "model-based clustering".
Check the two books on FMM:

*

*McLachlan, G. & Peel, D. (2000). Finite Mixture Models. John Wiley & Sons.

*Frühwirth-Schnatter, S. (2006). Finite Mixture and Markov Switching Models. Springer.

One of the most popular clustering packages that uses FMM is mclust (check here or here) that is implemented in R. However, more complicated FMM's are also possible, check for example flexmix package and it's documentation. For LCA there is an R poLCA package.
A: In addition to previous nice answers, I would suggest considering Dirichlet mixture models and Bayesian-based hierarchical Dirichlet process models. For a rather comprehensive and general overview of approaches and methods for determining an optimal number of clusters, please see this excellent answer on StackOverflow: https://stackoverflow.com/a/15376462/2872891.
A: A purely discriminative approach is "regularized information maximisation" by Gomes et al. There is no notion of similarity/distance involved in it whatsoever.
The idea is to have a logistic regression like model that puts points into bins. But instead of training it to maximise some form of log-likelihood of the class labels, the objective function is one that puts points into different clusters. 
To control the amount of clusters used by the model, an additional regularisation term weighted by the hyper parameter $\lambda$ is used. It boils down to a the inverse variance of a Gaussian prior over the weights.
Extension to kernel methods or neural networks for non-linear clustering is straightforward.
A: K-means isn't "really" distance based. It minimizes the variance. (But variance $\sim$ squared Euclidean distances; so every point is assigned to the nearest centroid by Euclidean distance, too).
There are plenty of grid-based clustering approaches. They don't compute distances because that would often yield quadratic runtime. Instead, they partition the data and aggregate it into grid cells. But the intuition behind such approaches is usually very closely related to distances.
There are a number of clustering algorithms for categorical data such as COOLCAT and STUCCO. Distances aren't easy to use with such data (one-hot encoding is a hack, and does not yield particularly meaningful distances). But I haven't heard of anyone using these algorithms...
There are clustering approaches for graphs. But either they reduce to classic graph problems such as clique or near-clique finding and graph coloring, or they are closely connected to distance-based clustering (if you have a weighted graph).
Density-based clustering like DBSCAN has a different name, and isn't focused around minimizing distances; but "density" is usually specified with respect to a distance, so technically these algorithms are either distance-based or grid-based.
The essential part of your question that you left out is what is your data?
