Indeed, you'll have to hack the client to be able to do that. The rules are not represented in the genesis block but in the client code.
You can change the divisibility with the constant "COIN" in main.h. "MAX_MONEY" will probably also be interesting to you. Note that coin amounts have to fit in signed 64 bit integers for the current implementation.
Also make sure that your network is not accepting packets from the current testnet or main chain by changing the identification bytes.
See also http://forum.bitcoin.org/index.php?topic=3051.0
and the other topics about the new testnet.