If we're including psychic communication, then one possibility is Olaf Stapledon's Star Maker from 1937. In this book a community of minds travels through the cosmos in disembodied form, viewing the history of intelligent life in the cosmos, which gradually starts to form larger and larger collective minds by means of some kind of psychic communication. But as for physical travel, all the methods described seem to be slower than light:
Hitherto, in spite of tentative telepathic exploration on the part of the most awakened worlds, the life of the galaxy had been in the main the life of a number of isolated worlds which took no effect upon one another. With the advent of interstellar travel the many distinct themes of the world-biographies gradually became merged in an all-embracing drama.
Travel within a planetary system was at first carried out by rocket-vessels propelled by normal fuels. In all the early ventures one great difficulty had been the danger of collision with meteors. Even the most efficient vessel, most skillfully navigated and traveling in regions that were relatively free from these invisible and lethal missiles, might at any moment crash and fuse. The trouble was not overcome till means had been found to unlock the treasure of sub-atomic energy. It was then possible to protect the ship by means of a far-flung envelope of power which either diverted or exploded the meteors at a distance. A rather similar method was with great difficulty devised to protect the space ships and their crews from the constant and murderous hail of cosmic radiation.
Interstellar, as opposed to interplanetary, travel was quite impossible until the advent of sub-atomic power. Fortunately this source of power was seldom gained until late in a world's development, when mentality was mature enough to wield this most dangerous of all physical instruments without inevitable disaster. Disasters, however, did occur. Several worlds were accidentally blown to pieces. In others civilization was temporarily destroyed. Sooner or later, however, most of the minded worlds tamed this formidable djin, and set it to work upon a titanic scale, not only in industry, but in such great enterprises as the alteration of planetary orbits for the improvement of climate. This dangerous and delicate process was effected by firing a gigantic sub-atomic rocket-apparatus at such times and places that the recoil would gradually accumulate to divert the planet's course in the desired direction.
Actual interstellar voyaging was first effected by detaching a planet from its natural orbit by a series of well-timed and well-placed rocket impulsions, and thus projecting it into outer space at a speed far greater than the normal planetary and stellar speeds. Something more than this was necessary, since life on a sunless planet would have been impossible. For short interstellar voyages the difficulty was sometimes overcome by the generation of sub-atomic energy from the planet's own substance; but for longer voyages, lasting for many thousands of years, the only method was to form a small artificial sun, and project it into space as a blazing satellite of the living world. For this purpose an uninhabited planet would be brought into proximity with the home planet to form a binary system. A mechanism would then be contrived for the controlled disintegration of the atoms of the lifeless planet, to provide a constant source of light and heat. The two bodies, revolving round one another, would be launched among the stars.
As for telepathy, when it is used to form a "galactic Utopia" of many minds in communion, it is said to not be hindered by distance:
Telepathic intercourse united the whole galaxy; but telepathy, though it had the great advantage that it was not affected by distance, was seemingly imperfect in other ways. So far as possible it was supplemented by physical travel.
Telepathy was used not just to join minds in communion but also to make observations. In an earlier phase before the galactic utopia, some worlds fell victim to a type of "madness" akin to totalitarianism where they sought to conquer other worlds to convert them to their own way of thinking, and it's said that some more advanced worlds used telepathy to monitor the progress of these mad empires:
Throughout this period of imperial expansion a few world-systems of a very high order ... had watched events telepathically from afar. They saw the frontiers of empire advancing steadily toward them, and knew that they themselves would soon be implicated.
After the imperial threat is ended by the telepathic intervention of a more advanced species from a "sub-galaxy" (I think referring to one of the globular clusters that orbits in the halo of the Milky Way, Stapledon was very up-to-date on the latest in cosmology), they use "telepathic communication" to spread their plans for reorganizing the minds of the galaxy to make a true galactic group mind possible, so presumably telepathy did allow for something more akin to communication than an immediate total joining of minds:
The worlds of the Sub-Galaxy, recognizing that no further great advance in culture was possible unless the population of awakened worlds was immensely increased and diversified, now began to play an active part in the work of reorganizing the whole galactic continent. By telepathic communication they gave to all awakened worlds throughout the galaxy knowledge of the triumphant society which they themselves had created; and they called upon all to join them in the founding of the galactic Utopia. Every world throughout the galaxy, they said, must be an intensely conscious individual; and each must contribute its personal idiosyncrasy and all the wealth of its experience to the pooled experience of all. When at last the community was completed, they said, it must go on to fulfil its function in the far greater community of all galaxies, there to participate in spiritual activities as yet but dimly guessed.
In their earlier age of meditation the Sub-Galactic worlds, or rather the single intermittently awakening mind of the Sub-Galaxy, had evidently made discoveries which had very precise bearing on the founding of the galactic society; for they now put forward the demand that the number of minded worlds in the Galaxy must be increased to at least ten thousand times its present extent. In order that all the potentialities of the spirit should be fulfilled, they said there must be a far greater diversity of world-types, and thousands of worlds of each type. They themselves, in their small Sub-Galactic community, had learned enough to realize that only a very much greater community could explore all the regions of being, some few of which they themselves had glimpsed, but only from afar.
Later, after the establishment of a single galactic group mind, telepathy was used to survey the minds in other galaxies prior to joining them in a larger communal mind:
Telepathic exploration had long ago revealed that at least in some other galaxies there existed minded worlds. And now, after long experiment, the worlds of our galaxy, working for this purpose as a single galactic mind, had attained much more detailed knowledge of the cosmos as a whole. ... After long and patient work, however, our galactic society succeeded in forming a fairly complete survey of the cosmical population of galaxies.
And in a later phase where the communal minds of different galaxies begin to join in an intergalactic community, there is a line (written from the perspective of our galaxy's cosmic mind) about the effects of the expansion of space driving galaxies apart which also makes clear that their telepathic communication must be faster than light:
I knew with exactness the sum of cosmical matter. And though the "expansion" of space was already sweeping most of the galaxies apart more swiftly than light could bridge the gulf, telepathic exploration still kept me in touch with the whole extent of the cosmos. Many of my own members were physically divided from one another by the insurmountable gulf created by the ceaseless "expansion"; but telepathically they were still united.
Another iffier possibility:
Stapledon's earlier 1930 book Last and First Men, which covered the future evolution and eventual extinction of humanity (which was briefly alluded to in Star Maker), also featured slower than light physical travel and some kind of mental communication which I think is implied to potentially work faster than light, but this isn't as clearly spelled out. In one section, the "Last Men" living on Neptune discover that a novel type of "infection" in a nearby star is soon going to spread to the Sun and make the solar system uninhabitable, so they make plans for a type of directed panspermia in which they transmit micro-organisms to other star systems, and this is apparently limited by the speed of light:
In respect of the future, we are now setting about the forlorn task of disseminating among the stars the seeds of a new humanity. For this purpose we shall make use of the pressure of radiation from the sun, and chiefly the extravagantly potent radiation that will later be available. We are hoping to devise extremely minute electro-magnetic "wave-systems," akin to normal protons and electrons, which will be individually capable of sailing forward upon the hurricane of solar radiation at a speed not wholly incomparable with the speed of light itself. This is a difficult task. But, further, these units must be so cunningly inter-related that, in favourable conditions,they may tend to combine to form spores of life, and to develop, not indeed into human beings, but into lowly organisms with a definite evolutionary bias toward the essentials of human nature. These objects we shall project from beyond our atmosphere in immense quantities at certain points of our planet's orbit, so that solar radiation may carry them toward the most promising regions of the galaxy.
The Last Men were also said to have "mind-detecting instruments" which they used to survey other forms of intelligent life throughout the galaxy, and there is this vague comment on how it works (which references an episode earlier in the book where the moon fell from its orbit for inexplicable reasons):
You may wonder how we have come to detect these remote lives and intelligences. I can say only that the occurrence of mentality produces certain minute astronomical effects, to which our instruments are sensitive even at great distances. These effects increase slightly with the mere mass of living matter on any astronomical body, but far more with its mental and spiritual development. Long ago it was the spiritual development of the world-community of the Fifth Men that dragged the moon from its orbit.
Their telepathy also allows them to re-experience the lives of beings of the past, and it's discovered that there is a type of backwards causality in which they are actually affecting some of those lives, so while this doesn't quite show that telepathy was intended to be faster than light (it could be that this can only be done within their own past light cone), it does at least suggest telepathy is not bound by the ordinary laws of causality:
We have long been able to enter into past minds and participate in their experience. Hitherto we have been passive spectators merely, but recently we have acquired the power of influencing past minds. This seems an impossibility; for a past event is what it is, and how can it conceivably be altered at a subsequent date, even in the minutest respect?
Now it is true that past events are what they are, irrevocably; but in certain cases some feature of a past event may depend on an event in the far future. The past event would never have been as it actually was (and is, eternally), if there had not been going to be a certain future event, which, though not contemporaneous with the past event, influences it directly in the sphere of eternal being. The passage of events is real, and time is the successiveness of passing events; but though events have passage, they have also eternal being. And in certain rare cases mental events far separated in time determine one another directly by way of eternity.
