  In area and depth, the Pan-STARRS1 (PS1) 3$\pi$ survey is unique among
many-epoch, multi-band surveys and has enormous potential for all-sky
identification of variable sources. PS1 has observed the sky typically seven
times in each of its five bands ($grizy$) over 3.5 years, but unlike SDSS not
simultaneously across the bands. Here we develop a new approach for quantifying
statistical properties of non-simultaneous, sparse, multi-color lightcurves
through light-curve structure functions, effectively turning PS1 into a $\sim
35$-epoch survey. We use this approach to estimate variability amplitudes and
timescales $(\omega_r, \tau)$ for all point-sources brighter than
$r_{\mathrm{P1}}=21.5$ mag in the survey. With PS1 data on SDSS Stripe 82 as
``ground truth", we use a Random Forest Classifier to identify QSOs and RR
Lyrae based on their variability and their mean PS1 and WISE colors. We find
that, aside from the Galactic plane, QSO and RR Lyrae samples of purity
$\sim$75\% and completeness $\sim$92\% can be selected. On this basis we have
identified a sample of $\sim 1,000,000$ QSO candidates, as well as an
unprecedentedly large and deep sample of $\sim$150,000 RR Lyrae candidates with
distances from $\sim$10 kpc to $\sim$120 kpc. Within the Draco dwarf
spheroidal, we demonstrate a distance precision of 6\% for RR Lyrae candidates.
We provide a catalog of all likely variable point sources and likely QSOs in
PS1, a total of $25.8\times 10^6$ sources.
