Update: There is a mention on Font patching. Maybe add a link to it in the installation section. :smile:
Update 2: urxvt is compiled with unicode3 in ubuntu but even so unpatched fonts won't work with it.
rxvt-unicode does not seem to honour fontconfig configurations so normal (unpatched) fonts do not use powerlinesymbols as fallback. See screenshot using regular Ubuntu Mono on the left.

Patched fonts (such as those from https://github.com/Lokaltog/powerline-fonts) work as expected.
My proposal is to update documentation to include an explanation on how urxvt is an expection and that patched fonts are needed. This would prevent users' frustation while trying to make new powerline work with rxvt. This seem to also apply to xterm.
Note: This is not only my case. See also Fontconfig fallback fonts are not used on a rxvt mailing list and Applications without fontconfig support.
Allright, I'll make this even clearer in the docs. I think the docs have to be restructured a bit too, since it seems that almost every terminal emulator has implemented its own way of handling fonts and the unicode Private Use Area.
Another note about uxrvt. I have observed that when patching "DejaVu Sans Mono", the resulting font does not have a good hinting. To avoid this, I have used the new font as a fallback of the regular font.
URxvt.font: xft:DejaVu Sans Mono-8,xft:DejaVu Sans Mono for Powerline-8
To decrease memory usage, I have also removed most glyphs from the patched font. Only some glyphs are left to allow urxvt to do boxsize computation:
# Remove most glyphs
for glyph in target_font.glyphs():
if glyph.unicode not in range(32,64):
target_font.removeGlyph(glyph)
Maybe this could be added as an option of the patcher script?
Most helpful comment
Another note about uxrvt. I have observed that when patching "DejaVu Sans Mono", the resulting font does not have a good hinting. To avoid this, I have used the new font as a fallback of the regular font.
To decrease memory usage, I have also removed most glyphs from the patched font. Only some glyphs are left to allow urxvt to do boxsize computation:
Maybe this could be added as an option of the patcher script?