How to Re-run failed JUnit tests immediately?

You can do this with a TestRule. This will give you the flexibility you need. A TestRule allows you to insert logic around the test, so you would implement the retry loop:

public class RetryTest {
    public class Retry implements TestRule {
        private int retryCount;

        public Retry(int retryCount) {
            this.retryCount = retryCount;
        }

        public Statement apply(Statement base, Description description) {
            return statement(base, description);
        }

        private Statement statement(final Statement base, final Description description) {
            return new Statement() {
                @Override
                public void evaluate() throws Throwable {
                    Throwable caughtThrowable = null;

                    // implement retry logic here
                    for (int i = 0; i < retryCount; i++) {
                        try {
                            base.evaluate();
                            return;
                        } catch (Throwable t) {
                            caughtThrowable = t;
                            System.err.println(description.getDisplayName() + ": run " + (i+1) + " failed");
                        }
                    }
                    System.err.println(description.getDisplayName() + ": giving up after " + retryCount + " failures");
                    throw caughtThrowable;
                }
            };
        }
    }

    @Rule
    public Retry retry = new Retry(3);

    @Test
    public void test1() {
    }

    @Test
    public void test2() {
        Object o = null;
        o.equals("foo");
    }
}

The heart of a TestRule is the base.evaluate(), which calls your test method. So around this call you put a retry loop. If an exception is thrown in your test method (an assertion failure is actually an AssertionError), then the test has failed, and you'll retry.

There is one other thing that may be of use. You may only want to apply this retry logic to a set of tests, in which case you can add into the Retry class above a test for a particular annotation on the method. Description contains a list of annotations for the method. For more information about this, see my answer to How to run some code before each JUnit @Test method individually, without using @RunWith nor AOP?.

Using a custom TestRunner

This is the suggestion of CKuck, you can define your own Runner. You need to extend BlockJUnit4ClassRunner and override runChild(). For more information see my answer to How to define JUnit method rule in a suite?. This answer details how to define how to run code for every method in a Suite, for which you have to define your own Runner.

As for me writing custom runner more flexible solution. The solution that posted above (with code example) has two disadvantages:

1. It won't retry test if it fails on the @BeforeClass stage;
2. It calculating tests run a bit differently (when you have 3 retries, you will receive test Runs: 4, success 1 that might be confusing);

That's why I prefer more approach with writing custom runner. And code of custom runner could be following:

import org.junit.Ignore;
import org.junit.internal.AssumptionViolatedException;
import org.junit.internal.runners.model.EachTestNotifier;
import org.junit.runner.Description;
import org.junit.runner.notification.RunNotifier;
import org.junit.runner.notification.StoppedByUserException;
import org.junit.runners.BlockJUnit4ClassRunner;
import org.junit.runners.model.FrameworkMethod;
import org.junit.runners.model.InitializationError;
import org.junit.runners.model.Statement;


public class RetryRunner extends BlockJUnit4ClassRunner {

    private final int retryCount = 100;
    private int failedAttempts = 0;

    public RetryRunner(Class<?> klass) throws InitializationError {
        super(klass);
    }    


    @Override
    public void run(final RunNotifier notifier) {
        EachTestNotifier testNotifier = new EachTestNotifier(notifier,
                getDescription());
        Statement statement = classBlock(notifier);
        try {

            statement.evaluate();
        } catch (AssumptionViolatedException e) {
            testNotifier.fireTestIgnored();
        } catch (StoppedByUserException e) {
            throw e;
        } catch (Throwable e) {
            retry(testNotifier, statement, e);
        }
    }

    @Override
    protected void runChild(final FrameworkMethod method, RunNotifier notifier) {
        Description description = describeChild(method);
        if (method.getAnnotation(Ignore.class) != null) {
            notifier.fireTestIgnored(description);
        } else {
            runTestUnit(methodBlock(method), description, notifier);
        }
    }

    /**
     * Runs a {@link Statement} that represents a leaf (aka atomic) test.
     */
    protected final void runTestUnit(Statement statement, Description description,
            RunNotifier notifier) {
        EachTestNotifier eachNotifier = new EachTestNotifier(notifier, description);
        eachNotifier.fireTestStarted();
        try {
            statement.evaluate();
        } catch (AssumptionViolatedException e) {
            eachNotifier.addFailedAssumption(e);
        } catch (Throwable e) {
            retry(eachNotifier, statement, e);
        } finally {
            eachNotifier.fireTestFinished();
        }
    }

    public void retry(EachTestNotifier notifier, Statement statement, Throwable currentThrowable) {
        Throwable caughtThrowable = currentThrowable;
        while (retryCount > failedAttempts) {
            try {
                statement.evaluate();
                return;
            } catch (Throwable t) {
                failedAttempts++;
                caughtThrowable = t;
            }
        }
        notifier.addFailure(caughtThrowable);
    }
}

Now there is a better option. If you're using maven plugins like: surfire or failsefe there is an option to add parameter rerunFailingTestsCount SurFire Api. This stuff was implemented in the following ticket: Jira Ticket. In this case you don't need to write your custom code and plugin automatically amend test results report.
I see only one drawback of this approach: If some test is failed on Before/After class stage test won't be re-ran.