I think I figured out what exactly I was missing. So, basically each of the new process groups should be defined at each of the processes before using them in any manner whatsoever.
A bit modified version of your example that most likely solves my purpose is the following:
import torch
import torch.multiprocessing as mp
import os


def run(rank, world_size):
    os.environ['MASTER_ADDR'] = 'localhost'
    os.environ['MASTER_PORT'] = '29500'
    # global group
    torch.distributed.init_process_group(backend='nccl',
                                         rank=rank,
                                         world_size=world_size)
    # torch.distributed.init_process_group(backend='gloo', init_method='env://')
    g0 = torch.distributed.new_group(ranks=[0, 2])
    g1 = torch.distributed.new_group(ranks=[1, 3])
    # tensor to bcast over group
    t = torch.tensor([1]).float().cuda().fill_(rank)
    if rank in [0, 2]:
        my_group = g0
    else:
        my_group = g1
    torch.distributed.all_reduce(t, group=my_group)
    print('rank: {} - val: {}'.format(rank, t.item()))


def main():
    world_size = 4
    mp.spawn(run, args=(world_size,), nprocs=world_size, join=True)


if __name__ == "__main__":
    main()


It works. 
Thanks again.