Exponential upper bound Suppose we have IID random variables $X_1,\dots,X_n$ with distribution $\mathrm{Ber}(\theta)$. We are going to observe a sample of the $X_i$'s in the following way: let $Y_1,\dots,Y_n$ be independent $\mathrm{Ber}(1/2)$ random variables, suppose that all the $X_i$'s and $Y_i$'s are independent, and define the sample size $N=\sum_{i=1}^n Y_i$. The $Y_i$'s indicate which of the $X_i$'s are in the sample, and we want to study the fraction of successes in the sample defined by
$$
  Z = \begin{cases}
      \frac{1}{N}\sum_{i=1}^n X_i Y_i & \text{if}\quad N > 0\, , \\
      0 & \text{if} \quad N = 0 \, .
      \end{cases}
$$
For $\epsilon>0$, we want to find an upper bound for $\mathrm{Pr}\!\left(Z \geq \theta + \epsilon\right)$ that decays exponentially with $n$. Hoeffding's inequality doesn't apply immediately because of the dependencies among the variables.
 A: Details to take care of the $N=0$ case.
$$
\begin{align}
  \{Z\geq\theta+\epsilon\} &= \left(\{Z\geq\theta+\epsilon\} \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\
&=  \left(\{0\geq\theta+\epsilon\} \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\
&=  \left(\emptyset \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\
&= \left\{\sum_{i=1}^n X_iY_i\geq(\theta+\epsilon)\sum_{i=1}^n Y_i\right\} \cap \{N>0\} \\
&\subset \left\{\sum_{i=1}^n X_iY_i\geq(\theta+\epsilon)\sum_{i=1}^n Y_i\right\} \\
&= \left\{\sum_{i=1}^n (X_i-\theta-\epsilon)Y_i\geq 0\right\} \\
&= \left\{\sum_{i=1}^n \left((X_i-\theta-\epsilon)Y_i+\epsilon/2\right)\geq n\epsilon/2\right\} \, .
\end{align}
$$
For Alecos.
$$
\begin{align}
\mathrm{E}\!\left[\sum_{i=1} ^n W_i\right]&=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i=0\}}\sum_{i=1} ^n W_i\right] + \mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\sum_{i=1} ^n W_i\right] \\
&=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\frac{\sum_{i=1} ^n Y_i}{\sum_{i=1}^n Y_i}\right]=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\right]=1-1/2^n \, .
\end{align}
$$
A: This answer keeps mutating. The current version does not relate to the discussion I had with @cardinal in the comments (although it was through this discussion that I thankfully realized that the conditioning approach did not appear to lead anywhere).  
For this attempt, I will use another part of Hoeffding's original 1963 paper, namely section 5 "Sums of Dependent Random Variables".
Set $$W_i \equiv \frac {Y_i}{\sum_{i=1}^nY_i}, \qquad \sum_{i=1}^nY_i \neq 0, \qquad \sum_{i=1}^nW_i=1, \qquad n\geq 2$$
while we set $W_i =0$ if $\sum_{i=1}^nY_i = 0$.
Then we have the variable
$$Z_n= \sum_{i=1}^nW_iX_i, \qquad E(Z_n) \equiv \mu_n$$
We are interested in the probability
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon), \qquad \epsilon < 1-\mu_n$$
As for many other inequalities, Hoeffding starts his reasoning by noting that 
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) = E\left[\mathbf 1_{\{Z_n-\mu_n -\epsilon \geq 0\}}\right]$$
and that 
$$\mathbf 1_{\{Z_n-\mu_n -\epsilon\geq 0\}} \leq \exp\Big\{h(Z_n-\mu_n -\epsilon)\Big\}, \qquad h>0$$
For the dependent-variables case, as Hoeffding we use the fact that $\sum_{i=1}^nW_i=1$ and invoke Jensen's inequality for the (convex) exponential function, to write
$$e^{hZ_n} = \exp\left\{h\left(\sum_{i=1}^nW_iX_i\right)\right\} \leq \sum_{i=1}^nW_ie^{hX_i}$$
and linking results to arrive at
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon)  \leq e^{-h(\mu_n+\epsilon)}E\left[\sum_{i=1}^nW_ie^{hX_i}\right]$$
Focusing on our case, since $W_i$ and $X_i$ are independent, expected values can be separated,
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon)  \leq e^{-h(\mu_n+\epsilon)}\sum_{i=1}^nE(W_i)E\left(e^{hX_i}\right)$$
In our case, the $X_i$ are i.i.d Bernoullis with parameter $\theta$, and $E[e^{hX_i}]$ is their common moment generating function in $h$, $E[e^{hX_i}] = 1-\theta +\theta e^h$. So
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon)  \leq e^{-h(\mu_n+\epsilon)}(1-\theta +\theta e^h)\sum_{i=1}^nE(W_i)$$
Minimizing the RHS with respect to $h$, we get
$$e^{h^*} = \frac {(1-\theta)(\mu_n+\epsilon)}{\theta(1-\mu_n-\epsilon)}$$
Plugging it into the inequality and manipulating we obtain
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon)  \leq \left(\frac {\theta}{\mu_n+\epsilon}\right)^{\mu_n+\epsilon}\cdot \left(\frac {1-\theta}{1-\mu_n-\epsilon}\right)^{1-\mu_n-\epsilon}\sum_{i=1}^nE(W_i)$$
while
$$\mathrm{Pr}(Z_n\geq \theta +\epsilon)  \leq \left(\frac {\theta}{\theta+\epsilon}\right)^{\theta+\epsilon}\cdot \left(\frac {1-\theta}{1-\theta-\epsilon}\right)^{1-\theta-\epsilon}\sum_{i=1}^nE(W_i)$$
Hoeffding shows that
$$\left(\frac {\theta}{\theta+\epsilon}\right)^{\theta+\epsilon}\cdot \left(\frac {1-\theta}{1-\theta-\epsilon}\right)^{1-\theta-\epsilon} \leq e^{-2\epsilon^2}$$
Courtesy of the OP (thanks, I was getting a bit exhausted...) 
$$\sum_{i=1}^n E(W_i) =1-1/2^n$$
So, finally, the "dependent variables approach" gives us
$$\mathrm{Pr}(Z_n\geq \theta +\epsilon)  \leq (1-\frac 1{2^n})e^{-2\epsilon^2} \equiv B_D$$
Let's compare this to Cardinal's bound, that is based on an "independence" transformation, $B_I$. For our bound to be tighter, we need
$$B_D=(1-\frac 1{2^n})e^{-2\epsilon^2} \leq e^{-n\epsilon^2/2}=B_I$$
$$\Rightarrow \frac {2^n-1}{2^n} \leq \exp\left\{\left(\frac {4-n}{2}\right)\epsilon^2\right\}$$
So for $n\leq 4$ we have $B_D \leq B_I$. For $n \geq 5$, pretty quickly $B_I$ becomes tighter than $B_D$ but for very small $\epsilon$, while even this small "window" quickly converges to zero. For example, for $n=12$, if $\epsilon \geq 0.008$, then $B_I$ is tighter. So in all, Cardinal's bound is more useful.  
COMMENT
To avoid misleading impressions regarding Hoeffding's original paper, I have to mention that Hoeffding examines the case of a deterministic convex combination of  dependent random variables. Specificaly, his $W_i$'s are numbers, not random variables, while each $X_i$ is a sum of independent random variables, while the dependency may exist between the $X_i$'s. He then considers various "U-statistics" that can be represented in this way.
A: We can draw a connection to Hoeffding's inequality in a fairly direct way.
Note that we have
$$
\{ Z > \theta + \epsilon\} = \big\{\sum_i X_i Y_i  > (\theta + \epsilon)\sum_i Y_i \big\} = \big\{ \sum_i (X_i - \theta - \epsilon) Y_i > 0 \} \>.
$$
Set $Z_i = (X_i - \theta - \epsilon)Y_i + \epsilon/2$ so that the $Z_i$ are iid, $\mathbb E Z_i = 0$ and
$$
\mathbb P( Z > \theta + \epsilon ) = \mathbb P\big(\sum_i Z_i > n \epsilon/2\big) \leq e^{-n \epsilon^2/2}\>,
$$
by a straightforward application of Hoeffding's inequality (since the $Z_i \in [-\theta-\epsilon/2,1-\theta-\epsilon/2]$ and so take values in an interval of size one).
There is a rich and fascinating related literature that has built up over the last several years, in particular, on topics related to random matrix theory with various practical applications. If you are interested in this sort of thing, I highly recommend:

R. Vershynin, Introduction to the non-asymptotic analysis of random
  matrices, Chapter 5 of Compressed
  Sensing, Theory and Applications. Edited by Y. Eldar and G. Kutyniok.
  Cambridge University Press, 2012.

I think the exposition is clear and provides a very nice way to get quickly acclimated to the literature.
