It sounds like you understand basically what you're trying to do, so this is more a programming puzzle than a security one, at this point.

If the buffer has the shellcode placed before the %Nu%n sequence, I won't know how many characters have been printed before I get to the first %n, since the shellcode will contain non-printable characters.

Getting the length of characters printed by just treating the shellcode itself as a format string is trivial: all the *printf functions return the number of characters printed, so just running int c = printf(<SHELLCODE>);printf("\n%d\n", c); will tell you how many characters are printed in the course of treating the shellcode as a format string. However, putting the shellcode before the format specifiers like this imposes a limit on the minimum value you could put with %n specifiers after the shellcode.

If it's placed after it, I won't know the address of the shellcode itself, since the amount of digits for each N may vary.

Easily solved by padding the string (with spaces, or zeroes, or whatever you want except format specifiers) between the format specifiers and the shellcode, and deleting a padding character every time a format specifier gets one character longer. In practice, since the number of digits in N will only change when you the value of N crosses a power of 10, you can also achieve this by just making minor tweaks.

If you want to make this really easy, pad the input string between your format specifiers and your shellcode with single-byte no-ops (the canonical one for x86 is 0x90), and then you only have to land somewhere between the end of the format specifiers (exclusive) and the start of the shellcode (inclusive), rather than on the start of the shellcode exactly. This technique is called a "NOP sled" because when the instruction pointer winds up anywhere in it, it just "slides" all the way into your shellcode.