В общем, если кому надо, накидал такой код, вроде должен работать. Поискал альтернативы, по сути примерно так все делают, для оптимизации производительности можно держать не один глобальный лок на map, а список (выбирать по хешу ключа), но тогда надо вместо HashMap ConcurrentHashMap использовать.

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

class LockMap {
    interface Unlockable {
        void unlock();
    }

    private final Lock locksLock = new ReentrantLock();
    private final Map<Object, ReferenceCountingLock> locks = new HashMap<Object, ReferenceCountingLock>();

    Unlockable lock(Object key) {
        boolean lockSuccessful = false;
        ReferenceCountingLock rcl = acquire(key);
        try {
            Unlocker unlocker = new Unlocker(key, rcl);
            rcl.lock.lock();
            lockSuccessful = true;
            return unlocker;
        } finally {
            if (!lockSuccessful) {
                release(key, rcl);
            }
        }
    }

    private ReferenceCountingLock acquire(Object key) {
        locksLock.lock();
        try {
            ReferenceCountingLock rcl = locks.get(key);
            if (rcl == null) {
                rcl = new ReferenceCountingLock();
                locks.put(key, rcl);
            }
            rcl.count++;
            return rcl;
        } finally {
            locksLock.unlock();
        }
    }

    private void release(Object key, ReferenceCountingLock rcl) {
        locksLock.lock();
        try {
            rcl.count--;
            if (rcl.count == 0) {
                ReferenceCountingLock oldRCL = locks.remove(key);
                if (rcl != oldRCL) {
                    throw new IllegalStateException();
                }
            }
        } finally {
            locksLock.unlock();
        }
    }

    private static class ReferenceCountingLock {
        private int count;
        private final Lock lock = new ReentrantLock();
    }

    private class Unlocker implements Unlockable {
        private final Object key;
        private final ReferenceCountingLock rcl;

        private Unlocker(Object key, ReferenceCountingLock rcl) {
            this.key = key;
            this.rcl = rcl;
        }

        @Override
        public void unlock() {
            try {
                rcl.lock.unlock();
            } finally {
                release(key, rcl);
            }
        }
    }
}

Использовать так же, как обычные локи:

        Unlockable lock = lockMap.lock(key);
        try {
           ...
        } finally {
            lock.unlock();
        }