Cannot deserialize JSON as abstract type?

I tried to get a solution for your problem, but I think the best one is yours : let the customer implement a getter with the name of its class, and pass it to your method as you first did. Because at the end of the day, no matter what you want, JSON absolutely needs the class name to deserialize a String into that class.

If you really want to make it simpler, make an abstract class with the ready-to-use method

public String Name(){
    return String.valueOf(this).split(':')[0];
}

and let the customer extend the class, focusing on the handle method...

EDIT

If you really really want to remove the name parameter, you might make an actual getter instead of the Name() method I wrote :

public abstract class AbstractFutureHandler{
    public String className{ get {
        return String.valueOf(this).split(':')[0];
    }}
}

and in FutureManager class :

@future
private static void Execute(String jsonHandle) {
    String typeName = (String) ( (Map<String, Object) JSON.deserializeUntyped(jsonHandle) ).get('className'); 
    FutureHandler handle = (FutureHandler)JSON.deserialize(jsonHandle, Type.forName(typeName)); 
    Execute_sync(handle);
} 

And finally

public class UpdateSomeRecords_future extends AbstractFutureHandler implements FutureHandler 
{ /* ... */ }

Kind of heavy, makes JSON deserialize twice but hey, Salesforce have servers, let's make them work ;)

If you want to deserialize into an interface, you still have to pass in a concrete type (the actual implementation). In this case, the following should work just fine:

FutureManager.execute('{...}', UpdateSomeRecords_future.class);
//                             ^ Concrete implementation type