Removing x-powered-by and changing cookies names for security?
Will it be against the terms and agreements of craft to remove those headers?
Will writing a plugin for it be the best way

No to both questions – just add the following config values to your /config/general.php file:
'sendPoweredByHeader' =&gt; false,
'phpSessionName' =&gt; 'WhateverYouWant',

Also, check out this excellent post by Brad Bell on the topic of Craft and security.