As we are not permitted to use anything else we start from the definition
$$\frac{te^{tx}}{e^t-1} = \sum_{n\ge 0} B_n(x) \frac{t^n}{n!}$$
and obtain
$$B_n(x) = \frac{n!}{2\pi i}
\int_{|t|=\epsilon}
\frac{1}{t^{n+1}} \frac{te^{tx}}{e^t-1} \; dt$$
and hence
$$[x^q] B_n(x) = \frac{n!}{q!\times 2\pi i}
\int_{|t|=\epsilon}
\frac{1}{t^{n+1}} \frac{t^{q+1}}{e^t-1} \; dt
\\ = \frac{n!}{q!\times 2\pi i}
\int_{|t|=\epsilon}
\frac{1}{t^{n-q+1}} \frac{t}{e^t-1} \; dt.$$
We see that this is zero for $q>n$
and moreover, $$[x^q] B_n(x) =
\frac{n!}{q!} \frac{B_{n-q}}{(n-q)!}
= {n\choose q} B_{n-q}.$$
This means we have reduced the problem of computing Bernoulli
polynomials to the problem of computing Bernoulli numbers, since as we
now know,
$$B_n(x) = \sum_{q=0}^n {n\choose q} B_{n-q} x^q.$$
This can be done by differentiating the generating function
$$\frac{t}{e^t-1} = \sum_{n\ge 0} B_n \frac{t^n}{n!}$$
to get
$$\frac{1}{e^t-1} - \frac{t}{(e^t-1)^2} e^t
= \sum_{n\ge 1} B_n \frac{t^{n-1}}{(n-1)!}.$$
The left is
$$\frac{1}{e^t-1}
- \frac{1}{e^t-1} \frac{te^t}{e^t-1}
\\ = \frac{1}{t}
+ \left(-\frac{1}{t} + \frac{1}{e^t-1}\right)
- \frac{1}{t} \frac{te^t}{e^t-1}
- \left(-\frac{1}{t} + \frac{1}{e^t-1}\right)
\frac{te^t}{e^t-1}.$$
Extracting coefficients from these exponential generating functions we
obtain for $n\ge 0$
$$B_{n+1} =
\frac{B_{n+1}}{n+1}
- \frac{B_{n+1}(1)}{n+1}
- \sum_{q=0}^n {n\choose q} \frac{B_{q+1}}{q+1} B_{n-q}(1).$$
Observe that
$$\frac{te^t}{e^t-1} = t + \frac{t}{e^t-1}$$
and hence
$$B_{n+1}(1) = B_{n+1}
\quad\text{except for}\quad
B_1(1) = 1 + B_1.$$
This gives for $n\ge 1$
$$B_{n+1} =
- {n\choose n-1} \frac{B_n}{n}
- \sum_{q=0}^n {n\choose q} \frac{B_{q+1}}{q+1} B_{n-q}
\\ = - B_n
- \frac{B_{n+1}}{n+1}
- \sum_{q=0}^{n-1} {n\choose q} \frac{B_{q+1}}{q+1} B_{n-q}$$
or
$$B_{n+1}\frac{n+2}{n+1}
= - B_n
- \sum_{q=0}^{n-1} {n\choose q} \frac{B_{q+1}}{q+1} B_{n-q}$$
and finally
$$B_{n+1} =
- \frac{n+1}{n+2} B_n
- \frac{n+1}{n+2}
\sum_{q=0}^{n-1} {n\choose q} \frac{B_{q+1}}{q+1} B_{n-q}.$$
This recurrence lets us calculate the $B_n$ starting from $B_0=1$ and
$B_1=-\frac{1}{2}.$
Addendum Wed Apr 22 22:47:07 CEST 2015. Since I did not have a
reference at hand when I wrote the above I failed to see that there is
a much simpler identity which results from writing
$$t = (e^t-1) \sum_{n\ge 0} B_n \frac{t^n}{n!}.$$
This is
$$t = e^t \sum_{n\ge 0} B_n \frac{t^n}{n!}
- \sum_{n\ge 0} B_n \frac{t^n}{n!}.$$
Extracting coefficients for $n\ge 2$ and observing the convolution of
two exponential generating functions in the first term we have
$$0 = \sum_{q=0}^n {n\choose q} B_q - B_n
= \sum_{q=0}^{n-1} {n\choose q} B_q.$$
This yields
$$B_{n-1} {n\choose n-1} =
-\sum_{q=0}^{n-2} {n\choose q} B_q$$
or $$B_{n-1} = -\frac{1}{n} \sum_{q=0}^{n-2} {n\choose q} B_q
\quad\text{or}\quad
B_m = -\frac{1}{m+1} \sum_{q=0}^{m-1} {m+1\choose q} B_q.$$