% based fees are not possible as the network doesn't know the size of the tx.

Also don't you think % base fees reek of old world thinking.  How much more does it cost to accept a 1,000,000 BTC tx than it does to accept a 100 BTC tx.

To answer your question the service you are looking to provide would be trivial.  I don't think anyone would use it but it simply requires you having a form and/or API where signed tx can be sent.  You need a modified bitcoind to verify the tx, and submit it to the network.  Checking for "delivery fee" is a little more work but not much.