The first one will not work. It's identical to johngg's solution, except missing the non-greedy quantifier after the first parenthesis. Thus it will only find the last match rather than all of them (and it will return it twice).
 

Your second regex works, and is probably the semantically cleanest solution posted so far. It also shouldn't be that slow, especially if the ratio of "fred" occurrences to the total length of the string is low. It can be generalized to arbitrary $n like this (note that the "!= 0" is redundant):

/fred(?(?{ (pos()-4) % $n })(?!))($capture)/g
[download]

However, if this regex is reused for multiple values of $n which is declared with my in the parent scope, it seems to keep using the first one (like a closure). Declaring the $n with our seems to fix this.

Your second regex works,

I'm not seeing that:

use strict;
use warnings;
use 5.010;

#      0    5   10   15   20   25   30   35
#      '    '    '    '    '    '    '    '
$_ = q{....fred1....fred2...fred3....fred4..};

while (/fred(?(?{ pos % 4 != 0 })(?!))(....)/sg) {

}

--output:--
Use of uninitialized value in numeric ne (!=) at (re_eval 1) line 1.
Use of uninitialized value in numeric ne (!=) at (re_eval 1) line 1.
Use of uninitialized value in numeric ne (!=) at (re_eval 1) line 1.
[download]

Ah yes, you need to add parenthesis after the pos (to make sure it is interpreted as a function without parameters):

/fred(?(?{ pos() % 4 != 0 })(?!))(....)/sg

I fixed that locally while testing ikegami's regex but then forgot about it when reporting back, sorry.

fred
(?              
    (?{ pos % 4 != 0 })
    (?!)
)
(....)
[download]

What does this construct do:

(?stuff)
[download]

I can't find anything about that in perlre.

Edit: Ah, the boolean test finally clued me in:

(?(condition)yes-pattern)
[download]

I can't find anything about that in perlre.

perlre is not exactly optimized for quickly finding out the meaning of a specific regex construct.

Use perlreref for that.