So you're partly right. Just tested the Nomad with different talismans on green LoL level 6 (average damage is his basic attack (2 hits) over 6 attacks):
Code:
Magic Build Attack Build Zero magic
Total Attack: 813 1494 813
Total Magic: 997 316 316
Sum: 1810 1810 1129
Avg damage dealt: 2200 4100 1750
So it seems his attack does scale with both magic & attack, but attack is more important (although this test is flawed since the attack build is stronger than the magic build... and made more difficult due to the 2 red slots & high base attack he has)
[THEORY: warriors w/true damage scale more w/attack, but Assassins scale evenly]
I also tested magic & physical charge: they only apply to magic or physical attacks, not to true damage. You'll notice when you magic charge, all your characters get a little blue light on their hands. The next magic attack will consume that charge (that is, on your next turn, your PDK will hit harder and the blue light will go away for him). The light never goes away for the Nomad, because he's doing true damage. The same is true for physical charge - it won't effect the Nomad or any other true damage attacker.
Don't know how the mechanics of Random damage though.