I am interested in pagan folk black metal bands, which use agressive tremolo picked riffing, guitar solos, and nice production...
Ensiferum like but more black pagan oriented
I liked Temnozor from Russia, Wyrd from Finland...
Anyone else knows similar artists?

You need to listen to Kroda, from Ukraine. Their music is awesome, and fits your criteria like a glove.

http://www.youtube.com/watch?v=8LhEGFGG1Ig

you should check belenos, magog (the german one) and arkona from poland.
they are not too folkish, but still have some of the greatest pagan spirit.

you might look into Myrkgrav's "Trollskau, Skrømt Og Kølabrenning". It might be a little too on the folksy side, but it surely contains the glorious tremolo riffs that you desire.

Kampfar, definitely.

Askival are a talented one man band from Scotland, who's black metal is mixed with folk and has Pagan themes. Very good debut, 'Eternity'. The first demo is darker in terms of the production, but is good also. I've heard them described as a mixture between Bathory and Nokturnal Mortum.

Perhaps not exactly what you're hoping for, but Peordh are another talented one man band.

Poccolus are recognised as one of the most underrated Pagan black metal bands of all time, as well as one of the best underground bands.

Darkestrah fuse black metal with folk and have Pagan themes running through the band.

General recommendations:
Oakhelm
Solgrav

http://www.metal-archives.com/band.php?id=17452

The band Horn from Germany. I don't know about others, but I believe this man can do NO wrong whatsoever with his pagan black metal. Naturkraft is simply beautiful. I haven't heard much pagan black metal, but I would say this is one of the best bands in the genre.

No shit.

I was also going to rec Horn, and totally agree with the above, simply stunning band at the top of their game, all the albums are fantastic, its just the same the band are not more known, as said they are one of the best black metal bands out there.

I know a couple pagan metal bands, but they aren't really black metal. Amon Amarth(sweeden) is really pagan, they have cool songs, and they're a combo of Dimmu Borgir and dethklok (thats the only way i can describe them)

Graveland you probably all ready know of graveland though

myrkgrav is amazing

drudkh?

Wyrd's Heathen.

Listen to Behemoth's first full length; Sventevith (Storming Near the Baltic).

I recommend Dark Forest (Canada). The reviews here seem to agree with me, too.

You'd probably like Drudkh. Their newest album, Microcosmos, is shaping up to be a winner.

Not so much with the guitar, but try Falkenbach. Amazing band.

Ceremonial Castings dosn't really do much real religion themed song, but they have on several occasions done songs on Witchcraft.

ghehehehe

OT:

Limbonic art might be what your looking for although they are super satanic

Thronar just to throw one into the mix. Good band from Belgium (I think) but they havent done much since their second album came out last year.

Immortal could in a way count as a Pagan Black Metal band. A lot of there songs deal with being in the North in the Mountains, the Rain, the Cold, the Oceans. A lot of it also talks about being a warrior and being known in the lands, almost viking like.

Maybe some Agalloch, Kromlek, Equilibrium, Finterforst, Black Messiah (though these bands are more vikingy)....

Hate Forest

You may like Helrunar, Minas Morgul and Wyrd.

Here are a few of my favorites which have not been mentioned yet:

Menhir (Ger) - The "Die Ewigen Steine" is one of my favorite albums of all time. Highly recommended!
Gontyna Kry (Pol) - Check out the "Welowie" demo, top notch material but very sloppy and poor production.
Black Moon (Chl) - Check out the song "Pagan Winds", should be on youtube.
Dub Buk (Ukr) - "Idu na Wy!" album, great black/speed mixture and great production. Why mention the rest of Ukrainian bands which are mostly based on pagan themes.
Briargh (Esp) - "Soledad" (third demo, 2004) Amazing stuff.
Hades (Nor) - (later Hades Almighty) anything from this band is flawless.
Kawir (Gre) - "Daimon" split has my favorite version of that song from this band.
Kalm (Est) - anything from this hidden gem, excellent stuff.

Edit: how can I forget? Abigor (Aus) - everything from these black metal geniuses.