There are “spatial index” data-structures for storing your circles for quick comparison later; Quadtree, r-tree and kd-tree are examples.
Solution 1 seems to be a spatial index, and solution 2 would benefit from a spatial index every time you recalculate your pairs.
To complicate matters, your objects are moving – they have velocity.
It is normal to use spatial indexes for objects in games and simulations, but mostly for stationary objects, and typically objects that don’t react to a collision by moving.
It is normal in games and such that you compute everything at set time intervals (discrete), so it might be that two objects pass through each other but you fail to notice because they moved so fast. Many games actually don’t even evaluate collisions in strict chronological order. They have a spatial index for stationary objects e.g. walls, and lists for all the moving objects that they check exhaustively (although with relaxed discrete checks as I outlined).
Accurate continuous collision detection and where the objects react to collisions in simulations is usually much more demanding.
The pairs approach you outlined sounds promising. You might keep the pairs sorted by next collision, and reinsert them when they have collided in the appropriate new positions. You only have to sort the new generated collision list (O(n lg n)) for the two objects and then to merge two lists (the new collisions for each object, and the existing list of collisions; inserting the new collisions, removing those stale collisions that listed the two objects that collided) which is O(n).
Another solution to this is to adapt your spatial index to store the objects not strictly in one sector but in each that it has passed through since the last calculation, and do things discretely. This means storing fast moving objects in your spatial structure, and you’d need to optimise it for this case.
Remember that linked lists or lists of pointers are very bad for caching on modern processors. I’d advocate that you store copies of your circles – their important properties for collision detection at any rate – in an array (sequential memory) in each sector of any spatial index, or in the pairs you outlined above.
As Mark says in the comments, it could be quite simple to parallelise the calculations.