Accelerators can charge what they want. Question is whether someone is going to use them.

Have you tried http://confirmtx.com/ or https://viabtc.com/tools/txaccelerator/ ?
Alternatively in service section are some users offering free acceleration as well.

Does mycelium offer you the option "replace by fee"? That would solve the problem. Otherwise I afraid you have to use bitcoin client, download entire blockchain and use console to rebroadcast tx.