The problem of searching for unmodeled gravitational-wave bursts can be thought of as a pattern recognition problem: how to find statistically significant clusters in spectrograms of strain power when the precise signal morphology is unknown. In a previous publication, we showed how “seedless clustering” can be used to dramatically improve the sensitivity of searches for long-lived (∼10–1000 s) gravitational-wave transients. To manage the computational costs, this initial analysis focused on externally triggered searches where the source location and emission time are both known to some degree of precision. In this paper, we show how the principle of seedless clustering can be extended to facilitate computationally feasible, all-sky searches where the direction and emission time of the source are entirely unknown. We further demonstrate that it is possible to achieve a considerable reduction in computation time by using graphical processor units, thereby facilitating more sensitive searches.