We present new identities involving Fibonacci and Bernoulli numbers, and Lucas and Euler numbers, respectively. To achieve this, we derive general relations between Bernoulli (Euler) polynomials and balancing (Lucas-balancing) polynomials. The derivations make use of elementary methods including generating functions and functional equations. Evaluating these polynomial relations at specific points, we get several new identities for the Fibonacci-Bernoulli and Lucas-Euler pairs. We also state some identities involving Bernoulli and balancing numbers.