For posterity, I've figured this one out:
1) The second method I described, actually works - but I was running as root and the rule "* soft nofile 65536" does not apply to root. Adding additional rules for root "root soft nofile 65536", "root hard nofile 65536" to /etc/security/limits.conf showed the change. Reboot was not required. Changing the limits for root wasn't strictly necessary for the problem I was having, but then it turns out, changing the limits at all wasn't required.....
2) The problem I was actually experiencing of mongo crashing due to lack of file descriptors was caused by bug is PyMongo 2.2. File descriptors were never being closed, so the crash is inevitable with enough time. See here:
https://groups.google.com/forum/#!topic/mongodb-user/BOmqWeHw8tc%5B1-25%5D. PyMongo 2.2.1 fixes this issue.