Template method pattern with arbitrary exception throwing

Let's say I have an abstract class Base that has a concrete method execute and three abstract methods stepOne, stepTwo and stepThree...

public abstract class Base {
    protected abstract void stepOne();
    protected abstract void stepTwo();
    protected abstract void stepThree();

    public final void execute() {
        //do stuff
        stepOne();
        //do stuff
        stepTwo();
        //do stuff
        stepThree();
        //do stuff
    }
}

...and is subclassed by a concrete class Sub1

public class Sub1 extends Base {
    protected void stepOne() {
        //...
    }

    protected void stepTwo() {
        //...
    }

    protected void stepThree() {
        //...
    }
}

Now let's suppose I have a second subclass Sub2 that can throw a checked exception in stepOne and stepTwo

public class Sub2 extends Base {
    protected void stepOne() throws Exception1 {
        //...
    }

    protected void stepTwo() throws Exception2 {
        //...
    }

    protected void stepThree() {
        //...
    }
}

I would like to use these classes as follows:

Sub1 s1 = new Sub1();
try {
    s1.execute();
} catch (Exception1 e1) {
    //handle e1
} catch (Exception2 e2) {
    //handle e2
}

Sub2 s2 = new Sub2();
s2.execute();

Clearly this doesn't work since the methods in Base aren't declared with any exceptions.

How can I have arbitrary exception throwing in the implementing classes? Is there a way without having to declare execute with throws Exception and always having to use a try-catch for it? I'd also like to avoid duplicating the common logic in execute into its subclasses. What's the best solution for this?