Generating a paper wallet would be pretty simple (since you are just generating a random password/id). The thing is, according to the NXT devs you really need to spend from an account/id to secure it (I guess that creates the public key?). Although, I do admit I'm not 100% sure how doing the spend really secures the account.
Your account number is 64 bits. So there could be many passwords (infinite actually) that result in the same 64 bit account ID. When you send an outgoing transaction, the account is no longer is protected just by 64 bit account ID, but by the 256 bit public key as the network now knows the public key for that account ID.
That's why it's required to send at least one outgoing transaction.
We don't need paper wallet. Just an app that does off line signing would make it close to 100% secure as the user is safe from keyloggers and malware. One outgoing transcation will still be needed, but that transaction can be signed on an offline computer that will never have internet connection.
