Using Symfony2's AccessDeniedHandlerInterface

This sounds about right.

Or, if you're specifically interested in AccessDeniedException you could also define access_denied_handler within your firewall in security.yml:

security:
    firewalls:
        my_firewall:
            # ...
            access_denied_handler: kernel.listener.access_denied.handler
            # ...

Then define your service in your services.xml or equivalent:

<parameters>
    <parameter key="kernel.listener.security.class">Path\To\Your\Class</parameter>
</parameters>

<service id="kernel.listener.access_denied.handler" class="%kernel.listener.security.class%">
    <tag name="kernel.event_listener" event="security.kernel_response" method="handle" />
</service>

The handler class:

use \Symfony\Component\Security\Http\Authorization\AccessDeniedHandlerInterface;

class MyAccessDeniedHandler implements AccessDeniedHandlerInterface
{
    public function handle(Request $request, AccessDeniedException $accessDeniedException)
    {
        // do something with your exception and return Response object (plain message of rendered template)
    }
}

You can find complete Security reference of Symfony2 here: http://symfony.com/doc/2.8/reference/configuration/security.html