So, I'm familiar with the "standard" explicit formula for the Bernoulli numbers:
$$B_m (n) = \sum^m_{k=0}\sum^k_{v=0}(-1)^v {k \choose v} {(n+v)^m \over k+1}$$
where choosing $n=0$ gives the Bernoulli numbers of the first kind and $n=1$ gives the Bernoulli numbers of the second kind. The term $(n+v)^m$ used in this formula basically means calculating Faulhaber's formula in a slight disguise, which of course depends on the Bernoulli numbers again. Wikipedia claims that the paper by Louis Saalschütz found at http://digital.library.cornell.edu/cgi/t/text/text-idx?c=math;idno=00450002 has some 38 other explicit formulae for the Bernoulli numbers, but unfortunately I can't read German and would not trust my understanding of the given formulae as a result. Is there any known explicit formula that doesn't rely on Faulhaber's formula the way the given formula does? Alternately, is there an English translation of that paper accessible anywhere?
I don't know if you have found your answer yet, but there is an expression
$$B_n=\sum_{j=1}^{n+1}\frac{(-1)^{j-1}}{j}{n+1\choose j}\sum_{i=0}^{j-1}(i|j)_n$$
in terms of falling factorials $(i|j)_n:=i(i-j)\cdots(i-(n-1)j)$ with increment $j$, which are similar but essentially relace $i^n$ with $(i|j)_n$. Reference is P.T. Young, "Bernoulli numbers and generalized factorial sums", Integers 11.4 (2011), 553-561. Hope this is helpful to you.