For feedforward networks, all-to-all connectivity seems to be what you're asking about. This is the standard/traditional way to construct a feedforward network (and is still in wide use). Local connectivity with shared weights (i.e. convolutional networks) are a more recent development. The local connections in convnets impose the assumption that there is local structure to exploit, and the shared weights impose the assumption that this structure is translation invariant. In return, the number of parameters is drastically reduced, which can help prevent overfitting. If your data don't satisfy these assumptions and you don't otherwise have a way to constrain the network architecture, then all-to-all connectivity may be your best bet. As you mention, the increased complexity may necessitate other kinds of constraints (e.g. regularization) to reduce overfitting if the network is large relative to the amount of data you're able to train on.
Recurrent networks can be thought of as feedforward networks that are unrolled in time, where temporally adjacent layers are connected via a shared set of weights, and each layer has its own input/output. 'Temporally global' connections don't make much sense when picturing the network in its recurrent form. But, there are architectures (e.g. LSTMs) where certain units act as memory buffers, feeding their values forward through time. I suppose you could think of this as achieving a similar effect to a 'temporally global' connection.
It should be mentioned: just because connections are constrained to be local doesn't mean that a network can only learn local structure. For example, early layers in convnets do, indeed, learn local features (it would be impossible for them to learn global features). But, higher layers--with only local connections to their respective inputs--learn compositions of these features, which tend to be more global with respect to the input space. For example, in image processing convnets, lower level layers learn features like local edge detectors, and higher level layers learn global features/concepts like faces, cats, and dogs, which span many pixels in the input space. Conversely, even all-to-all connected networks tend to learn local edge detectors in the early layers. In the temporal domain, recurrent networks can learn long timescale patterns despite connections being 'temporally local', because the recurrent connections propagate information forward in time. However, architectures with special memory units have tended to be more successful in learning very long timescale dependencies because they're better able to cope with the vanishing gradient problem.
Regarding your question about randomly permuting the input: If the input is something like images, then a feedforward network with all-to-all connectivity could work, and scrambling the input would have no effect compared to training the same network on the original input. In fact, early layers might very well learn local features in the original image space (which you could see if you unscrambled them). If the input is a time series, a recurrent network no longer makes sense because the temporal information has been destroyed. In this case, you might be able to treat individual sequences as input vectors to a feedforward network with all-to-all connectivity.